# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
986045 | AlphaMale06 | The Big Prize (IOI17_prize) | C++17 | 51 ms | 600 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;
//vector<int> ask(int i);
int find_best(int n){
if(n<=5000){
for(int i=0; i<n; i++){
vector<int> ans = ask(i);
if(ans[0]==0 && ans[1]==0)return i;
}
}
int summ = 0;
for(int i=0; i<10; i++){
int ind = rand()%n;
vector<int> ans = ask(ind);
summ=max(summ, ans[0]+ans[1]);
if(ans[0]==0 && ans[1]==0)return ind;
}
int prev=-1;
for(int i=0; i<summ; i++){
int l = prev+1, r = n-1;
int best = n-1;
while(l<=r){
int s = l+r>>1;
vector<int> ans = ask(s);
if(ans[0]+ans[1]==0)return s;
if(ans[0]+ans[1]==summ){
if(ans[0]>i){
best=s-1;
r=s-1;
}
else l=s+1;
}
else{
best = s;
r=s-1;
}
}
vector<int> ans = ask(best);
prev=best;
if(ans[0]+ans[1]==0)return best;
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |