Submission #265137

#TimeUsernameProblemLanguageResultExecution timeMemory
265137arayiThe Big Prize (IOI17_prize)C++17
20 / 100
94 ms672 KiB
#include "prize.h" #include <bits/stdc++.h> #define MP make_pair #define fr first #define sc second using namespace std; mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); const int N = 2e5 + 55; vector <pair <int, int> > dz; bool col[N]; int mx, q; int as(int a) { q++; if(q == 9800) { assert(0); } vector <int> fp = ask(a); if(fp[0] + fp[1] == 0) return 0; if(!col[a] && fp[0] + fp[1] < mx) { dz.push_back(MP(a, fp[0] + fp[1])); return 2; } int sm = 0; for(auto p : dz) if(p.fr < a && p.sc < fp[0] + fp[1]) sm++; if(fp[0] - sm) return -1; return 1; } int find_best(int n) { for (int i = 0; i < 200; i++) { int i1 = rnd() % n; vector <int> fp = ask(i1); mx = max(mx, fp[0] + fp[1]); } while(true) { int l = 0, r = n - 1; while(l <= r) { int mid = (l + r)/2; int sm = as(mid); if(sm == 0) return mid; if(sm == 2) { col[mid] = true; break; } if(sm == 1) l = mid + 1; if(sm == -1) r = mid - 1; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...