Submission #69346

#TimeUsernameProblemLanguageResultExecution timeMemory
69346Noam527The Big Prize (IOI17_prize)C++17
97.02 / 100
83 ms1152 KiB
#include "prize.h" #include <bits/stdc++.h> #define endl '\n' #define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) #define debug cout << "ok" << endl #define finish(x) return cout << x << endl, 0 typedef long long ll; typedef long double ldb; const int md = 1e9 + 7, inf = 1e9 + 7; const ll hs = 199; const ldb eps = 1e-9, pi = acos(-1); using namespace std; /* vector<int> ask(int i) { cout << "? " << i << endl; vector<int> rtn(2); cin >> rtn[0] >> rtn[1]; return rtn; } */ map<int, vector<int>> alreadyfound; vector<int> Q(int i) { if (alreadyfound.count(i)) return alreadyfound[i]; return alreadyfound[i] = ask(i); } int N, badval; bool bad(vector<int> a) { return a[0] + a[1] == badval; } bool answer(vector<int> a) { return a[0] + a[1] == 0; } // finds next bad position after pos. assumes it exists. pair<int, vector<int>> findnext(int pos) { vector<int> a; while (!bad(a = Q(pos))) { if (answer(a)) return{ pos, a }; pos++; } return{ pos, a }; } // returns the ? in (val, val, ?, val + 1, ...). ? is the first in the sequence. int calc(int l, int r, int val) { pair<int, vector<int>> b; int mid; while (l < r) { mid = (l + r + 1) / 2; b = findnext(mid); if (answer(b.second)) return b.first; if (val < b.second[0]) r = mid - 1; else l = mid; } return l; } int find_best(int n) { alreadyfound.clear(); vector<int> a; if (n <= 5000) { for (int i = 0; i < n; i++) { a = ask(i); if (a[0] + a[1] == 0) return i; } } for (int i = 0; i < 500; i++) { auto something = Q(i); if (answer(something)) return i; badval = max(badval, something[0] + something[1]); } N = n; int l = 0, r = n - 1; while (!bad(a = Q(l))) { if (answer(a)) return l; l++; } while (!bad(a = Q(r))) { if (answer(a)) return r; r--; } int st = l, en, cnt; pair<int, vector<int>> b; while (st <= r) { en = min(r, st + 512); b = findnext(st); if (answer(b.second)) return b.first; st = b.first; b = findnext(en); if (answer(b.second)) return b.first; cnt = b.second[0] - Q(st)[0] - (b.first - en); for (int i = 0, tmp; i < cnt; i++) { tmp = calc(st, en, Q(st)[0] + i); if (answer(Q(tmp))) return tmp; if (answer(Q(tmp + 1))) return tmp + 1; } st = b.first; } return -1; } /* int main() { int n; cin >> n; cout << find_best(n) << endl; cout << "^ is my answer" << endl; } */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...