Submission #715830

#TimeUsernameProblemLanguageResultExecution timeMemory
715830bin9638The Big Prize (IOI17_prize)C++17
0 / 100
10 ms412 KiB
#include<bits/stdc++.h> #ifndef SKY #include "prize.h" #endif // SKY using namespace std; #define N 200010 #define ll long long #define ii pair<int,int> #define fs first #define sc second #define pb push_back #define iii pair<int,ii> int n,lolipop; #ifdef SKY int p[N]; vector<int> ask(int i) { cout<<"ask "<<i<<endl; vector<int>res(2,0); for(int j=0;j<i;j++) if(p[j]<p[i]) res[0]++; for(int j=i+1;j<n;j++) if(p[j]<p[i]) res[1]++; // cout<<i<<endl; // for(int j=0;j<n;j++)cout<<p[j]<<" ";cout<<endl; // cout<<res[0]<<" "<<res[1]<<endl; return res; } #endif // SKY int query=0; vector<int>myAsk(int i) { assert(i>=0&&i<n); vector<int>res=ask(i); query++; return res; } vector<int>lis; void solve(int l,int r) { int lef=0,righ=0; while(l<=r) { vector<int>s=myAsk(l); if(s[0]+s[1]!=lolipop) { lis.pb(l); l++; }else { lef=s[0]; break; } } while(r>=l) { vector<int>s=myAsk(r); if(s[0]+s[1]!=lolipop) { lis.pb(r); r--; }else { righ=s[1]; break; } } if(l>r) return; int mid=(l+r)/2; vector<int>s=myAsk(mid); if(s[0]+s[1]!=lolipop) { lis.pb(lolipop); solve(l,mid-1); solve(mid+1,r); return; } if(s[0]-lef!=0) { solve(l,mid-1); } if(s[1]-righ!=0) { solve(mid+1,r); } } int find_best(int cc) { n=cc; lis.clear(); if(n<=7) { for(int i=0;i<n;i++) { vector<int>s=myAsk(i); if(s[0]==0&&s[1]==0) return i; } } lolipop=0; for(int i=0;i<sqrt(n)*2;i++) { vector<int>s=myAsk(i); lolipop=max(lolipop,s[0]+s[1]); } //cout<<lolipop<<endl; solve(0,n-1); for(auto i:lis) { vector<int>s=myAsk(i); if(s[0]==0&&s[1]==0) return i; } } #ifdef SKY int main() { freopen("A.inp","r",stdin); freopen("A.out","w",stdout); ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); int n; cin>>n; for(int i=0;i<n;i++) cin>>p[i]; cout<<find_best(n); cout<<endl<<query<<endl; return 0; } #endif // SKY

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:126:1: warning: control reaches end of non-void function [-Wreturn-type]
  126 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...