| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 255030 | tinjyu | 커다란 상품 (IOI17_prize) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
int m,ball=0,a[200005][2],ans=-1,tag[1000005];
int find(int x)
{
if(a[x][0]==-1)
{
std::vector<int> res = ask(x);
a[x][0]=res[0];
a[x][1]=res[1];
}
return 0;
}
int solve(int s,int e){
//cout<<s<<" "<<e<<endl;
if(s>=e-1)return 0;
if(ans!=-1)return 0;
int ne,ns,c1=1,c2=1;
ne=(s+e)/2,ns=(s+e)/2;
while(ns<e)
{
find(ns);
if(a[ns][0]+a[ns][1]==0)
{
ans=ns;
return 0;
}
if(a[ns][0]+a[ns][1]!=ball)
{
if(a[ns][0]+a[ns][1]>ball)
{
ball=a[ns][0]+a[ns][1];
break;
}
if(a[ns][1]==0)
{
c1=0;
break;
}
ns++;
}
else break;
}
while(s<ne)
{
find(ne);
if(a[ne][0]+a[ne][1]==0)
{
ans=ne;
break;
}
if(a[ne][0]+a[ne][1]!=ball)
{
if(a[ne][0]+a[ne][1]>ball)
{
ball=a[ne][0]+a[ne][1];
break;
}
if(a[ne][0]==0)
{
c2=0;
break;
}
ne--;
}
else break;
}
//cout<<ne<<" "<<ns<<endl;
if(c1==1 && a[ns][1]!=a[e][1])solve(ns,e);
if(c2==1 && a[s][0]!=a[ne][0])solve(s,ne);
}
int find_best(int n) {
for(int i=0;i<n;i++)
{
a[i][0]=-1;
a[i][1]=-1;
}
for(int t = 0; t < 200; t++) {
long long int i=rand();
i%=n;
while(tag[i]==1)
{
i=rand();
i%=n;
}
tag[i]=1;
find(i);
//cout<<a[i][0]<<" "<<a[i][1]<<endl;
if(a[i][0]+a[i][1]==0)
{
ans=i;
break;
}
if(a[i][0] + a[i][1] > ball)
{
m=i;
ball=a[i][0]+a[i][1];
}
}
if(ans!=-1)return ans;
// cout<<m<<endl;
int start=0,end=n-1;
while(true)
{
find(start);
if(a[start][0]+a[start][1]==0)ans=start;
if(a[start][0]+a[start][1]!=ball)
{
if(a[start][0]+a[start][1]>ball)
{
ball=a[start][0]+a[start][1];
break;
}
start++;
}
else break;
}
while(true)
{
find(end);
if(a[end][0]+a[end][1]==0)ans=end;
if(a[end][0]+a[end][1]!=ball)
{
if(a[en][0]+a[end][1]>ball)
{
ball=a[en][0]+a[end][1];
break;
}
end--;
}
else break;
}
if(ans!=-1)return ans;
//cout<<start<<" "<<end<<endl;
solve(start,m);
solve(m,end);
return ans;
}