This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define pi pair<int,int>
#define f first
#define s second
const int MAX = 2e5;
int ans[MAX][2];
int a;
pi query(int pos){
if(ans[pos][0]!=-1) return {ans[pos][0], ans[pos][1]};
auto hold = ask(pos);
ans[pos][0] = hold[0];
ans[pos][1] = hold[1];
if(hold[0]+hold[1]==0){
a = pos;
}
return {hold[0],hold[1]};
}
int sum(int pos){
query(pos);
return ans[pos][0]+ ans[pos][1];
}
void solve(int l, int r){
if(a!=-1) return;
if(l==r){
query(l);
}
while(sum(l)!= sum(r)){
if(sum(l)< sum(r)) l++;
else r--;
}
if(ans[l][0]==ans[r][0]) return;
int m = (l+r)/2;
solve(l,m);
solve(m,r);
}
int find_best( int n ) {
for(int i = 0; i < n; i++){
ans[i][0]=-1;
}
a=-1;
solve(0,n-1);
return a;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |