| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 50721 | zetapi | 동굴 (IOI13_cave) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "cave.h"
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define mp make_pair
const int MAX=1e5;
void exploreCave(int N)
{
/* ... */
vector<int> vec;
int cur,lol,shi[MAX],pos[MAX];
for(int A=0;A<N;A++)
{
shi[A]=0;
pos[A]=0;
vec.pb(A);
}
for(int A=0;A<N;A++)
{
cur=tryCombination(shi);
if(cur==-1)
{
for(auto B:vec)
{
shi[B]=1;
pos[B]=tryCombination(shi);
shi[B]=0;
}
answer(shi,pos);
return ;
}
/*for(auto B:vec)
{
shi[B]=1;
lol=tryCombination(shi);
if(lol>cur or lol==-1)
{
shi[B]=1;
pos[B]=cur;
vec.erase(lower_bound(vec.begin(),vec.end(),B));
break;
}
else if(lol<cur)
{
shi[B]=0;
pos[B]=lol;
vec.erase(lower_bound(vec.begin(),vec.end(),B));
break;
}
shi[B]=0;
}*/
int low=0,high=vec.size()-1,mid,res=0;
while(low<=high)
{
mid=(low+high)/2;
for(auto B:vec)
{
if(B<=vec[mid])
shi[B]=1;
else
shi[B]=0;
}
lol=tryCombination(shi);
if(lol!=cur)
{
res=mid;
high=mid-1;
}
else
low=mid+1;
for(auto B:vec)
shi[B]=0;
}
int B=vec[res];
shi[B]=1;
lol=tryCombination(B);
if(lol>cur or lol==-1)
{
shi[B]=1;
pos[B]=cur;
vec.erase(lower_bound(vec.begin(),vec.end(),B));
}
else if(lol<cur)
{
shi[B]=0;
pos[B]=lol;
vec.erase(lower_bound(vec.begin(),vec.end(),B));
}
}
answer(shi,pos);
return ;
}