제출 #778869

#제출 시각아이디문제언어결과실행 시간메모리
778869kingfran1907커다란 상품 (IOI17_prize)C++14
20 / 100
3073 ms1992 KiB
#include "prize.h" #include <bits/stdc++.h> #define X first #define Y second using namespace std; typedef long long llint; const int maxn = 2e5+10; int l[maxn], r[maxn]; int out = -1; int maxi = 0; pair<int,int> query(int x) { if (l[x] != -1) return {l[x], r[x]}; vector< int > v = ask(x); l[x] = v[0], r[x] = v[1]; return {l[x], r[x]}; } llint ra() { return (llint)rand() * rand() + rand(); } void solve(int l, int r) { if (l > r) return; if (out != -1) return; if (query(l).X + query(l).Y == 0) { out = l; return; } if (query(l).X + query(l).Y < maxi) {solve(l + 1, r); return;} if (l == r) return; if (query(r).X + query(r).Y == 0) { out = r; return; } if (query(r).X + query(r).Y < maxi) {solve(l, r - 1); return;} if (query(l).X == query(r).X) return; int mid = (l + r) / 2; solve(l, mid); solve(mid, r); } int find_best(int n) { memset(l, -1, sizeof l); srand(13); for (int i = 0; i < 200; i++) { int x = ra() % n; pair<int, int> tr = query(x); if (tr.X + tr.Y == 0) return x; maxi = max(maxi, tr.X + tr.Y); } solve(0, n - 1); assert(out != -1); return out; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...