| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 429122 | vanic | 커다란 상품 (IOI17_prize) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "prize.h"
#include <iostream>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <vector>
#include <set>
#include <unistd.h>
#include <cassert>
using namespace std;
const int maxn=2e5+5;
const int mod=1e9+7;
const int cap=1000;
ll raand(){
return rand()%mod*rand()%mod;
}
int sum;
bool asked[maxn];
int uk;
int nadji(int L, int D, int vall, int vald){
int mid=(L+D)/2;
vector < int > v={-1, -1};
while(mid<D && v[0]+v[1]!=sum){
if(!asked[mid]){
uk++;
v=ask(mid);
asked[mid]=1;
if(!v[0] && !v[1]){
return mid;
}
}
mid++;
}
if(v[0]+v[1]!=sum){
mid=(L+D)/2;
while(mid>=L && v[0]+v[1]!=sum){
if(!asked[mid]){
uk++;
v=ask(mid);
asked[mid]=1;
if(!v[0] && !v[1]){
return mid;
}
}
mid--;
}
if(v[0]+v[1]!=sum){
return -1;
}
uk--;
mid++;
}
else{
uk--;
mid--;
}
assert(uk<cap);
int br=-1;
if(v[0]-vall){
br=nadji(L, mid, vall, v[1]);
if(br!=-1){
return br;
}
}
if(v[1]-vald){
br=nadji(mid+1, D, v[0], vald);
}
return br;
}
set < int > svi;
set < int > jaki;
int find_best(int n){
srand(time(NULL));
vector < int > v;
int pos;
if(n>5000){
for(int i=0; i<440; i++){
do{
pos=rand()%n;
}while(svi.find(pos)!=svi.end());
v=ask(pos);
svi.insert(pos);
if(!v[0] && !v[1]){
return pos;
}
if(v[0]+v[1]==sum){
jaki.insert(pos);
}
else if(v[0]+v[1]>sum){
jaki.clear();
jaki.insert(pos);
sum=v[0]+v[1];
}
}
while(!jaki.empty()){
svi.erase(*jaki.begin());
jaki.erase(jaki.begin());
}
while(!svi.empty()){
asked[*svi.begin()]=1;
svi.erase(svi.begin());
}
int a=nadji(0, n, 0, 0);
assert(a!=-1);
return a;
}
else{
for(int i=0; i<n; i++){
v=ask(i);
if(!v[0] && !v[1]){
return i;
}
}
}
}