| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 283044 | MohamedAhmed04 | The Big Prize (IOI17_prize) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "prize.h"
#include "grader.cpp"
using namespace std ;
const int MAX = 2e5 + 10 ;
vector<int>val[MAX] ;
int cnt = 0 ;
vector<int> Ask(int idx)
{
if(val[idx].size() == 0)
{
cnt++ ;
assert(cnt <= 10000) ;
val[idx] = ask(idx) ;
}
return val[idx] ;
}
int find_best(int n)
{
int maxcnt = 0 ;
for(int i = 0 ; i < 1 ; ++i)
{
Ask(i) ;
maxcnt = max(maxcnt , val[i][0] + val[i][1]) ;
if(val[i][0] + val[i][1] == 0)
return i ;
}
int st = -1 ;
for(int i = 0 ; i < 500 ; ++i)
{
if(val[i][0] + val[i][1] == maxcnt)
{
st = i ;
break ;
}
}
assert(st != -1) ;
vector<int>v ;
for(int i = st ; i < n-1 ; ++i)
{
int l = i , r = n-1 ;
int idx = n-1 ;
while(l <= r)
{
int mid = (l + r) >> 1 ;
v = Ask(mid) ;
if(v[0] == val[i][0] && v[1] == val[i][1])
idx = mid , l = mid+1 ;
else
r = mid-1 ;
}
for(int j = idx+1 ; j < n ; ++j)
{
Ask(j) ;
if(val[j][0] + val[j][1] == val[i][0] + val[i][1])
{
i = j-1 ;
break ;
}
if(val[j][0] == 0 && val[j][1] == 0)
return j ;
}
}
}