Submission #1057352

#TimeUsernameProblemLanguageResultExecution timeMemory
1057352shenfe1The Big Prize (IOI17_prize)C++17
100 / 100
32 ms2464 KiB
#include <bits/stdc++.h> #include "prize.h" using namespace std; #define pb push_back #define pii pair<int,int> #define sz(s) (int)s.size() #define F first #define S second #define all(v) v.begin(),v.end() const int MAX=2e5+10; bool use[MAX]; pii res[MAX]; int cq; pii cnt(int pos){ if(use[pos])return res[pos]; use[pos]=1; cq++; vector<int> v=ask(pos); return res[pos]={v[0],v[1]}; } int sum(int pos){ pii c=cnt(pos); return c.F+c.S; } mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int rnd(int l,int r){ return rng()%(r-l+1)+l; } int cntMx; int find_best(int n){ cntMx=0; int L=500; int r=0; // cout<<r<<"\n"; for(int j=0;j<min(n,L);j++){ cntMx=max(cntMx,sum(j)); r++; if(sum(j)==0)return j; if(cntMx*cntMx+1>n){ // cout<<j<<'\n'; break; } } // cout<<r<<" "<<cq<<"\n"; int pref=0; for(int j=0;j<r;j++){ if(sum(j)!=cntMx)pref++; } queue<pair<pii,pii>> q; q.push({{r,n-1},{cntMx,pref}}); while(!q.empty()){ int l=q.front().F.F,r=q.front().F.S,c=q.front().S.F,pl=q.front().S.S; q.pop(); // cout<<cq<<"\n"; if(c==0)continue; if(c==r-l+1){ // cout<<"??\n"; for(int i=l;i<=r;i++){ if(sum(i)==0){ return i; } } continue; } // cout<<l<<" "<<r<<" "<<c<<" "<<pl<<"\n"; int tl=(l+r)/2,tr=(l+r)/2; // cout<<sum(tl)<<" "<<cntMx<<"\n"; while(tl>=l&&sum(tl)!=cntMx){ if(sum(tl)==0){ return tl; } tl--; } while(tr<=r&&sum(tr)!=cntMx){ if(sum(tr)==0){ return tr; } tr++; } // cerr<<tl<<" "<<tr<<"\n"; if(tl>=l){ int L=cnt(tl).F-pl; if(l<=tl-1)q.push({{l,tl-1},{L,pl}}); } if(tr<=r){ int R=c-cnt(tr).F+pl; if(tr+1<=r){ q.push({{tr+1,r},{R,cnt(tr).F}}); } } } return -1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...