#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
vector<int>vec;int N,Query=0;
pair<int,int> asks(int p){
Query++;
vector<int>Z = ask(p);
return make_pair(Z[0],Z[1]);
}
int find_best(int n) {
srand((unsigned)time(NULL));
N=n;
vector<int>vec;for(int i=0;i<n;i++) vec.push_back(i);
while(vec.size()>=2){
int minx=0;
if(vec.size()>=30){
for(int i=0;i<5;i++){
pair<int,int>A=asks(vec[rand()%vec.size()]);
minx=max(minx,A.first+A.second);
}
}
else{
for(int i=0;i<vec.size();i++){
pair<int,int>A=asks(vec[i]);
minx=max(minx,A.first+A.second);
}
}
int s = 0;for(int i=0;i<20;i++){if((1<<i)<=vec.size()) s=i+1;}
int cnt=0,ret=-1;vector<int>vec2;
while(true){
int c = 0;
for(int i=s-1;i>=0;i--){
int pos = vec[min(c + (1<<i), (int)vec.size() - 1)];
if(pos <= ret) c += (1<<i);
else{
pair<int,int>Z = asks(pos);
if(Z.first+Z.second==minx && Z.first<=cnt) c+=(1<<i);
}
}
if(c==(1<<s)-1){
break;
}
else{
// results = vec[c + 1]
if(c == 0 && ret == -1){
int pos = vec[0];
pair<int, int> Z = asks(pos);
if(Z.first + Z.second != minx) c = -1;
}
vec2.push_back(vec[c + 1]);
ret = vec[c + 1];
}
cnt++;
}
vec=vec2;
}
assert(false);
return vec[0];
}
Compilation message
prize.cpp: In function 'int find_best(int)':
prize.cpp:27:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<vec.size();i++){
~^~~~~~~~~~~
prize.cpp:33:44: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
int s = 0;for(int i=0;i<20;i++){if((1<<i)<=vec.size()) s=i+1;}
~~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
2280 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
2548 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
