이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define N ((int)201*1000)
int n,arr[N],a[N],sz,lft[N],rght[N];
int cnt_rght[N],cnt_lft[N];
bool mark[N];
bool query(int x)
{
if(lft[x]+rght[x]>0)return 0;
vector <int> vec;vec=ask(x);
lft[x]=vec[0];rght[x]=vec[1];
return (lft[x]+rght[x]==0);
}
void add(int x)
{
mark[x]=1;
for(int i=x+1;i<n;i++)cnt_lft[i]++;
for(int i=x-1;i>=0;i--)cnt_rght[i]++;
return ;
}
int find_best(int n2)
{
n=n2;
for(int i=0;i<n;i++)arr[i]=i;
srand(69);
random_shuffle(arr,arr+n);
int now=0,id;
for(int i=0;i<600;i++)
{
if(query(arr[i]))return arr[i];
if(now<lft[arr[i]]+rght[arr[i]])
now=lft[arr[i]]+rght[arr[i]],id=arr[i];
}
for(int i=0;i<600;i++)
if(now>lft[arr[i]]+rght[arr[i]])
add(arr[i]);
while(1)
{
sz=0;
for(int i=0;i<n;i++)
if(!mark[i])
a[sz++]=i;
a[sz]=n;
int l=-1,r=sz;
while(l<r-1)
{
int mid=(l+r)/2;
if(query(a[mid]))return a[mid];
if(lft[a[mid]]+rght[a[mid]]<now)
{
add(a[mid]);
break;
}
if((rght[a[mid]]-cnt_rght[a[mid]])-(rght[a[r]]-cnt_rght[a[r]])>0)l=mid;
else r=mid;
}
}
}
컴파일 시 표준 에러 (stderr) 메시지
prize.cpp: In function 'int find_best(int)':
prize.cpp:33:12: warning: variable 'id' set but not used [-Wunused-but-set-variable]
int now=0,id;
^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |