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/e6f6341a-8e37-4aac-be64-ac45d142bc8e%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
