| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 70065 | E869120 | 커다란 상품 (IOI17_prize) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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));
for(int i=0;i<N;i++) R[i]=make_pair(-1,-1);
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=0;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){
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(Query<=10000);
return vec[0];
}