제출 #964731

#제출 시각아이디문제언어결과실행 시간메모리
964731AdamGS커다란 상품 (IOI17_prize)C++17
100 / 100
32 ms7388 KiB
#include "prize.h" #include<bits/stdc++.h> using namespace std; #define rep(a, b) for(int a = 0; a < (b); ++a) #define st first #define nd second #define pb push_back #define all(a) a.begin(), a.end() const int LIM=2e5+7; vector<int>P[LIM]; int odw[LIM], ma, n; void pytaj(int x) { if(odw[x]) return; odw[x]=1; P[x]=ask(x); ma=max(ma, P[x][0]+P[x][1]); } bool dobry(int x) { if(x<0 || x>=n) return false; pytaj(x); return P[x][0]+P[x][1]<ma; } bool wygrany(int x) { if(x<0 || x>=n) return false; pytaj(x); return P[x][0]+P[x][1]==0; } int solve(int l, int r) { if(l>r) return -1; if(wygrany(l-1)) return l-1; if(dobry(l-1)) return solve(l+1, r); if(wygrany(r+1)) return r+1; if(dobry(r+1)) return solve(l, r-1); int a=ma; if(l) a=P[l-1][1]; if(r<n-1) a-=P[r+1][1]; if(!a) return -1; int mid=(l+r)/2; if(wygrany(mid)) return mid; int p=solve(l, mid-1); if(p!=-1) return p; return solve(mid+1, r); } int find_best(int N) { n=N; if(n<=5000) { rep(i, n) { pytaj(i); if(P[i][0]+P[i][1]==0) return i; } } int x=n/500; rep(i, 499) if(wygrany(x*(i+1))) return x*(i+1); int p=solve(0, x-1); if(p!=-1) return p; rep(i, 498) { p=solve(x*(i+1)+1, x*(i+2)-1); if(p!=-1) return p; } return solve(x*499+1, n-1); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...