이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
vector<int> v;
map<int,pair<int,int> > mp;
bool check[200005],ok;
int ans,mx,N;
void dfs(int x, int y){
if(x>y || y>=N || ok==1) return;
int a,b,c,d;
if(check[x]==1){
a=mp[x].ff;
b=mp[x].ss;
}
else{
vector<int> v1=ask(x);
a=v1[0];
b=v1[1];
check[x]=1;
mp[x].ff=a;
mp[x].ss=b;
if(a+b==0){
ok=1;
ans=x;
return;
}
}
if(x==y){
if(a+b!=mx) v.pb(x);
return;
}
if(check[y]==1){
c=mp[y].ff;
d=mp[y].ss;
}
else{
vector<int> v2=ask(y);
c=v2[0];
d=v2[1];
mp[y].ff=c;
mp[y].ss=d;
check[y]=1;
if(c+d==0){
ok=1;
ans=y;
return;
}
}
if(a+b==mx && c+d==mx){
if(c-a==0 || y-x==1) return;
int mid=(x+y)/2;
dfs(x,mid);
dfs(mid+1,y);
}
else{
if(a+b<mx && c+d<mx){
v.pb(x);
v.pb(y);
if(y-x>=3){
int mid=((y-1)+(x+1)/2);
dfs(x+1,mid);
dfs(mid+1,y-1);
}
if(y-x==2){
dfs(x+1,x+1);
}
return;
}
if(a+b<mx){
v.pb(x);
if(x+1<y){
int mid=(x+1+y)/2;
dfs(x+1,mid);
dfs(mid+1,y);
}
return;
}
v.pb(y);
if(x<y-1){
int mid=(x-1+y)/2;
dfs(x,mid);
dfs(mid+1,y-1);
}
}
}
int find_best(int n) {
N=n;
for(int i=0; i<min(480,n); i++){
vector<int> vv;
vv=ask(i);
if(vv[0]+vv[1]==0){
return i;
}
check[i]=1;
mp[i].ff=vv[0];
mp[i].ss=vv[1];
mx=max(mx,vv[0]+vv[1]);
}
int l=0;
int r=n-1;
dfs(l,r);
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |