| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 390575 | faresbasbs | The Big Prize (IOI17_prize) | C++14 | 0 ms | 0 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<vector<int>> p[200001];
vector<int> askk(int pos){
if(p[pos].size()){
return p[pos];
}
return p[pos] = ask(pos);
}
int find_best(int n){
int sum = 0;
for(int i = 0 ; i < 450 ; i += 1){
int a = rand()%n;
vector<int> v = askk(a);
sum = max(sum,v[0]+v[1]);
if(v[0]+v[1] == 0){
return a;
}
}
vector<pair<int,vector<int>>> v;
int p = 0;
while(p < n){
while(p < n){
vector<int> f = askk(p);
if(f[0]+f[1] == sum){
v.push_back({p,f});
break;
}else{
if(f[0]+f[1] == 0){
return p;
}
p += 1;
}
}
p += 450;
}
v.push_back({n,{sum,0}});
for(int i = 0 ; i+1 < v.size() ; i += 1){
while(v[i+1].second[0] != v[i].second[0]){
int first = v[i].first , last = v[i+1].first;
while(last-first > 1){
int mid = (first+last)/2;
vector<int> f = askk(mid);
if(f[0]+f[1] == 0){
return mid;
}
if(f[0]+f[1] == sum && f[0] == v[i].second[0]){
first = mid;
}else{
last = mid;
}
}
vector<int> f;
for(int j = first+2 ; j < n ; j += 1){
f = askk(j);
if(f[0]+f[1] == 0){
return j;
}
if(f[0]+f[1] == sum){
v[i] = {j,f};
break;
}
}
}
}
}
/*int main(){
cout << find_best(8) << endl;
}*/