It is technically possible that your program would run into a dead loop.
Inside function `Count(double low, double high, const vector<Item>& data)`,
if your `low` and `high` is big, say around 1e10, and they are very close to
each other, such that (low + high) * 0.5 is either low or high, but high - low
> 1e-11 (due to precision lost in double), and low and high give different
order of data
your program will keep calling Count(low, high, data) indefinitely.
I cant think of a sample data that would make it happen though.
> Dear all,
>
> I want to know why I receive a TLE for the small data set with the
> program below. All your help are appreciated! (I failed to reproduce the
> RE/TLE myself. So I need an exact data set that fails to work.)
>
> Or is there any difference between the judge environment and by PC?
>
> P.S. No need to point me to the good solution. I've got one myself, sadly
> only 30 mins after the round completes.
>
> Regards,
> WC Leung.
>
>
> #include <stdint.h>
> #include <algorithm>
> #include <cmath>
> #include <iomanip>
> #include <iostream>
> #include <map>
> #include <string>
> #include <queue>
> #include <vector>
>
> using namespace std;
>
> struct Item {
> int a;
> int b;
> int index;
> };
>
> double factor = 0.0;
>
> vector<Item> data1;
> vector<Item> data2;
>
> bool compare(Item left, Item right) {
> double l = factor * left.a + 1.0 * left.b;
> double r = factor * right.a + 1.0 * right.b;
> return l < r || (l == r && left.index < right.index);
> }
>
> int Count(double low, double high, const vector<Item>& data) {
> data1 = data;
> data2 = data;
> factor = low;
> sort(data1.begin(), data1.end(), compare);
> factor = high;
> sort(data2.begin(), data2.end(), compare);
>
> bool same = true;
> for (int i = 0; i < (int) data.size(); ++i) {
> if (data1[i].index != data2[i].index) {
> same = false;
> break;
> }
> }
>
> if (!same) {
> if (high - low < 0.00000000001)
> return 1;
>
> double mid = (low + high) * 0.5;
> int count = Count(low, mid, data) + Count(mid, high, data);
> return count;
> }
>
> return 0;
> }
>
> void solve(int caseNo) {
> std::cout << "Case #" << caseNo << ": ";
>
> int n;
> cin >> n;
>
> vector<Item> data;
>
> for (int i = 0; i < n; ++i) {
> Item item;
> cin >> item.a >> item.b;
> item.index = i;
>
> data.push_back(item);
> }
>
> cout << (Count(0.00000000001, 100000000000, data) + 1) << "\n";
> }
>
> int main(int argc, char** argv) {
> int N;
> std::cin >> N;
> std::string str;
> std::getline(std::cin, str);
>
> for (int i = 0; i < N; ++i) {
> solve(i + 1);
> }
>
> return 0;
> }
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/6d38f7c7-ca5d-4e3a-b909-bb9275590432%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
