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;
int mx = 0;
int ans = -1;
void search(int ll, int lr, int rl, int rr, int cl, int cr, int c){
if (ans != -1 || c == 0) return;
int CL, CR;
if (ll < 0 || rr < 0 || rl < 0 || lr < 0 || ll > rr) return;
//printf("search <%d,%d><%d,%d>, <%d,%d>, %d\n",ll,lr,rl,rr,cl,cr,c);
if (ll == rr){
vector<int> p = ask(ll);
CL = p[0], CR = p[1];
if (CL + CR != mx){ /// is special
if (CL == 0 && CR == 0) ans = ll;
}
return;
}
int q = (rr-rl)>(lr-ll)?rl:lr;
vector<int> p = ask(q);
CL = p[0], CR = p[1];
if (CL + CR != mx){ /// is special
if (CL == 0 && CR == 0) {
ans = q; return;
}
else{
if (q == lr){
search(ll, lr-1, rl, rr, cl, cr, c-1);
}
else if (q == rl){
search(ll, lr, rl+1, rr, cl, cr, c-1);
}
}
return;
}
CR -= cr;
CL -= cl;
if (q == lr){
int L, R, mid;
L = ll, R = lr-1;
mid = (L+R)/2;
search(L, mid, mid+1, R, cl, CR + cr, CL);
L = rl, R = rr;
mid = (L+R)/2;
search(L, mid, mid+1, R, CL + cl, cr, CR);
}
else{
int L, R, mid;
L = ll, R = lr;
mid = (L+R)/2;
search(L, mid, mid+1, R, cl, CR + cr, CL);
L = rl+1, R = rr;
mid = (L+R)/2;
search(L, mid, mid+1, R, CL + cl, cr, CR);
}
}
int find_best(int n) {
for (int i = 0; i < min(n,231); i++){
vector<int> p = ask(i);
//if (p[0] == 0 && p[1] == 0) return i;
mx = max(mx,p[0]+p[1]);
}
int L, R;
L = 0, R = n-1;
int mid = (L+R)/2;
search(L, mid, mid+1, R, 0, 0, mx);
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |