# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
103106 | minson123 | The Big Prize (IOI17_prize) | C++11 | 0 ms | 0 KiB |
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<bits/stdc++.h>
#include "prize.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int pos;
map<int,pii> dic;
pii query(int p){
if(dic.find(p)!=dic.end()) return dic[p];
vector<int> q=ask(p);
return dic[p]=pii(q[0],q[1]);
}
vector<int> solve(int l,int r,vector<int> tar){
if(pos!=-1) return vector<int>({0,0});
if(l==r){
vector<int> q=query(l);
if(q[0]==0 && q[1]==0 && pos==-1) pos=l;
return q;
}
int mid=(l+r)>>1;
vector<int> q=query(mid+1);
if(q[0]==0 && q[1]==0 && pos==-1) pos=mid+1;
if(pos!=-1) return vector<int>({0,0});
if(q[0]!=tar[0] || q[1]!=tar[1]) tar=solve(mid+1,r,tar);
if(pos!=-1) return vector<int>({0,0});
return solve(l,mid,tar);
}
int find_best(int n){
pos=-1;
vector<int> q=query(n-1);
if(q[0]==0 && q[1]==0) return n-1;
solve(0,n-1,q);
return pos;
}