Submission #1227454

#TimeUsernameProblemLanguageResultExecution timeMemory
1227454The_SamuraiThe Big Prize (IOI17_prize)C++20
90 / 100
173 ms1268 KiB
#include "prize.h" #include "bits/stdc++.h" using namespace std; int find_best(int n) { int worst = 0; auto vec = ask(worst); int exp = vec[0] + vec[1]; if (exp == 0) return 0; for (int i = 1; i < min(500, n); i++) { auto shit = ask(i); if (shit[0] + shit[1] == 0) return i; if (shit[0] + shit[1] > exp) { exp = shit[0] + shit[1]; vec = shit; worst = i; } } vector<bool> blocked(n); auto find_next = [&](int worst) -> int { int best = -1; deque<int> d; for (int i = worst; i < n; i++) if (!blocked[i]) d.push_back(i); while (!d.empty()) { int mid = d.size() / 2; auto shit = ask(d[mid]); // cout << d.size() << ' ' << d[mid] << ' ' << shit[0] << ' ' << shit[1] << endl; if (shit[0] + shit[1] == 0) return d[mid]; if (vec[0] + vec[1] != shit[0] + shit[1]) { blocked[d[mid]] = true; d.erase(d.begin() + mid); continue; } if (vec == shit) { best = d[mid]; for (int i = 0; i <= mid; i++) d.pop_front(); } else { while (mid < d.size()) d.pop_back(); } } assert(best != -1); return best; }; worst = find_next(worst); vec = ask(worst); if (vec[0] + vec[1] == 0) return worst; while (true) { for (int i = worst + 1; i < n; i++) { auto shit = ask(i); if (shit[0] + shit[1] == 0) return i; if (shit[0] + shit[1] == vec[0] + vec[1]) { vec = shit; worst = i; break; } } // cout << '\t' << worst << ' ' << vec[0] << ' ' << vec[1] << endl; worst = find_next(worst); vec = ask(worst); if (vec[0] + vec[1] == 0) return worst; } // assert(false); return -1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...