이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "prize.h"
#include <iostream>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <vector>
#include <unistd.h>
#include <cassert>
using namespace std;
const int maxn=2e5+5;
int sum;
bool asked[maxn];
int nadji(int L, int D, int vall, int vald){
assert(L!=D);
// cout << L << ' ' << D << endl;
int br=0;
int pos;
vector < int > v={-1, -1};
do{
int br1=0;
do{
pos=rand()%(D-L)+L;
br1++;
}while(asked[pos] && br1<100);
if(!asked[pos]){
v=ask(pos);
asked[pos]=1;
if(!v[0] && !v[1]){
return pos;
}
}
br++;
}while(br<100 && v[0]+v[1]!=sum);
if(v[0]+v[1]!=sum){
// assert(D-L<1000);
br=0;
for(int i=L; i<D; i++){
if(!asked[i]){
asked[i]=1;
v=ask(i);
if(!v[0] && !v[1]){
return i;
}
if(v[0]+v[1]==sum){
br++;
}
}
}
assert(br<(D-L)/2);
return -1;
}
br=-1;
if(v[0]-vall){
br=nadji(L, pos, vall, v[1]);
if(br!=-1){
return br;
}
}
if(v[1]-vald){
br=nadji(pos+1, D, v[0], vald);
}
return br;
}
int find_best(int n){
srand(time(NULL)*getpid());
vector < int > v;
int pos;
do{
pos=rand()%n;
v=ask(pos);
if(!v[0] && !v[1]){
return pos;
}
}while(v[0]+v[1]<n/2);
sum=v[0]+v[1];
int a=nadji(0, n, 0, 0);
assert(a!=-1);
return a;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |