제출 #780018

#제출 시각아이디문제언어결과실행 시간메모리
780018Evirir커다란 상품 (IOI17_prize)C++14
20 / 100
83 ms24752 KiB
#include "prize.h" #include<bits/stdc++.h> using namespace std; #define pb push_back #define fi first #define se second #define sz(a) (int)(a.size()) #define all(a) a.begin(),a.end() typedef pair<int,int> pii; int loli = 0; vector<vector<int>>memo(222222,{-1,-1}); vector<int>glo; auto query(int x){ if(memo[x][0] == -1)memo[x] = ask(x); glo = memo[x]; return memo[x]; } int ans = 0; void solve(int l,int r,int cntl,int cntr){ //cout<<l<<" "<<r<<" "<<cntl<<" "<<cntr<<'\n'; int mid = (l+r)/2; int L = -1,R = -1; for(int i=mid;i>=l;i--){ auto res = query(i); assert(glo == res); if(glo[0]+glo[1] == 0){ ans = i; return; } if(glo[0]+glo[1] != loli)continue; L = i; break; } if(L!=-1){ auto res = query(L); assert(glo == res); int x = mid-L; if(glo[0] - cntl)solve(l,L-1,cntl,glo[1]); if(glo[1] - cntr - x)solve(mid+1,r,glo[0] + x,cntr); return; } /// for(int i=mid+1;i<=r;i++){ auto res = query(i); assert(glo == res); if(glo[0]+glo[1] == 0){ ans = i; return; } if(glo[0]+glo[1] != loli)continue; R = i; break; } if(R == -1)return; auto res = query(R); assert(glo == res); if(glo[1] - cntr)solve(R+1,r,glo[0],cntr); } int find_best(int n) { memo = vector<vector<int>>(222222,{-1,-1}); int p = 0; for(int i=0;i<min(n,477);i++){ auto res = query(i); assert(glo == res); if(glo[0]+glo[1] == 0)return i; if(glo[0]+glo[1] > loli){ loli = glo[0]+glo[1]; p = i; } if(loli >= 27)break; } solve(p,n-1,p,0); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...