제출 #778865

#제출 시각아이디문제언어결과실행 시간메모리
778865kingfran1907커다란 상품 (IOI17_prize)C++14
20 / 100
71 ms1820 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]}; } 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 + 1, mid); solve(mid + 1, r - 1); } int find_best(int n) { memset(l, -1, sizeof l); for (int i = 0; i < min(500, n); i++) { pair<int, int> tr = query(i); if (tr.X + tr.Y == 0) return i; maxi = max(maxi, tr.X + tr.Y); } solve(500, n - 1); assert(out != -1); return out; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...