이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
int ma,mma;
pair<int,int> ret[200005];
int lt(int i){
if(ret[i].first==-1){
vector<int>x=ask(i);
ret[i]=make_pair(x[0],x[1]);
}
return ret[i].first;
}
int rt(int i){
if(ret[i].second==-1){
vector<int>x=ask(i);
ret[i]=make_pair(x[0],x[1]);
}
return ret[i].second;
}
int ss(int i){
return lt(i)+rt(i);
}
int type(int i){
int x=ss(i);
if(x==0)return i;
else if(ma<x){
mma=x;
return -1;
}else if(ma==x)return -2;
else return -3;
}
void left(int l,int &i){
while(l<=i&&type(i)==-3)i--;
}
void right(int r,int &i){
while(i<=r&&type(i)==-3)i++;
}
int solve(int l,int r,int s,int t){
if(r<l)return -3;
if(l==r)return type(l);
int ml=(l+r)/2,mr=ml;
left(l,ml);
int res=-3;
if(l<=ml&&type(ml)>=-1)return type(ml);
if(l<ml&&s-rt(ml)>0)res=solve(l,ml-1,s,rt(ml));
if(res>=-1)return res;
right(r,mr);
if(mr<=r&&type(mr)>=-1)return type(mr);
if(mr<r&&rt(mr)-t>0)res=solve(mr+1,r,rt(mr),t);
return res;
}
int find_best(int n){
for(int i=0;i<n;i++)ret[i]=make_pair(-1,-1);
for(int i=0;i<400;i++){
if(type(i)>=0)return type(i);
ma=mma;
}
while(1){
ma=mma;
int la=400;
right(n-1,la);
if(type(la)>=0)return type(la);
if(type(la)==-1)continue;
while(1){
int pl=min(la+256,n-1),pr=pl;
left(la,pl);
if(type(pl)>=0)return type(pl);
if(type(pl)==-1)break;
int res=solve(la+1,pl-1,rt(la),rt(pl));
if(res>=0)return res;
if(res==-1)break;
right(n-1,pr);
if(type(pr)>=0)return type(pr);
if(type(pr)==-1)return -1;
la=pr;
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |