제출 #1199361

#제출 시각아이디문제언어결과실행 시간메모리
1199361didododi커다란 상품 (IOI17_prize)C++20
90 / 100
61 ms9884 KiB
#include "prize.h" #include <bits/stdc++.h> //#define int long long #define pii pair<int,int> #define vi vector<int> #define ff first #define ss second #define sp << " " << #define all(x) x.begin(),x.end() using namespace std; const int inf = 2e9; map<int,vi> cache; int asked = 0; set<int> possible; vi askeys; vi myask(int p) { if (cache.count(p)) return cache[p]; asked++; askeys.push_back(p); cache[p] = ask(p); if (cache[p][0]+cache[p][1]) possible.erase(p); return cache[p]; } int find_best(int n) { int mx = 0; srand(time(0)); int select; for (int i = 0;i<500 && i<n;i++) { vi v = myask(i); if (v[0]+v[1] == 0) return i; if (v[0]+v[1] > mx) { mx = v[0]+v[1]; select = i; } } int pr = select; for (int i = select+1;i<n;i++) possible.insert(i); for (auto it : askeys) { vi vvv = myask(it); if (vvv[0]+vvv[1]) possible.erase(it); else return it; } while (possible.size()+asked > 3000) { if (pr >= n-1) break; vector<int> q = myask(pr); vi prv = myask(pr+1); if (prv[0]+prv[1] == 0) return pr+1; if ((prv[0]+prv[1]) != (q[0]+q[1])) { int ptr = pr+1; possible.erase(ptr); while (ptr < n-1) { prv = myask(ptr+1); if (prv[0]+prv[1] == 0) return ptr+1; if ((prv[0]+prv[1]) != (q[0]+q[1])) ptr++; else break; } pr = ptr+1; continue; } int l = pr+1; int r = min(n-1,pr+500); while (l<=r) { int m = (l+r) >> 1; vi vv = myask(m); if (vv[0]+vv[1] == 0) return m; if ((vv[0]+vv[1] != q[0]+q[1]) || (vv[0] > q[0])) r = m-1; else l = m+1; } for (int j = pr;j <= r;j++) possible.erase(j); pr = r; } vi v(all(possible)); shuffle(all(v),mt19937_64(0)); for (auto it : v) { vi vv = myask(it); if (vv[0] + vv[1] == 0) return it; } assert(0); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...