Submission #1062483

#TimeUsernameProblemLanguageResultExecution timeMemory
1062483Faisal_SaqibThe Big Prize (IOI17_prize)C++17
90 / 100
62 ms428 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define vll vector<ll> #define all(x) begin(x),end(x) #define pb push_back std::vector<int> ask(int i); int find_best(int n) { int ans=-1; int i=0; auto it1=ask(0); while(1) { // cout<<"Starting from "<<i<<endl; int s=i,e=n; auto lasp=it1; if(lasp[0]==0 and lasp[1]==0) return i; while(s+1<e){ int mid=(s+e)/2; auto it=ask(mid); // cout<<"Checking "<<mid<<endl; // cout<<it1[0]<<' '<<it1[1]<<endl; // cout<<it[0]<<' '<<it[1]<<endl; if((it1[0]==it[0] and it1[1]==it[1])) { s=mid; } else{ int cur_sum=it[0]+it[1]; int back_sum=it1[0]+it1[1]; // We want to know if there is any element greater than i in the [i,mid] if(back_sum<cur_sum) { // it is smaller than current element // can't solve from here // ll rp=rand()%2; // if(rp) // s=mid; // Recursively call for both side // or maybe stop binary search e=i+1; lasp=ask(i+1); break; } else{ e=mid; lasp=it; } } // if((it[0]+it[1])!=((it1[0]+it1[1]))) // { // e=mid; // } // else{ // // if max(a1,a2,a3,..,an) <= k // // if this is the case // // then it1[1]==it[1] // // also it1[0]==it[0] // s=mid; // } } // cout<<"Solved for "<<i<<' '<<s<<' '<<e<<endl; if(e==n) { break; } i=e; it1=lasp; } return i; }

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:13:9: warning: unused variable 'ans' [-Wunused-variable]
   13 |     int ans=-1;
      |         ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...