# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1124314 | Rainmaker2627 | 동굴 (IOI13_cave) | C++20 | 0 ms | 0 KiB |
#include "cave.h"
void setPrefix(int N, int l, int r, int (&s)[], int (&cor)[]) {
for (int i = 0; i < l; ++i) s[i]=(cor[i]==-1?1-r:cor[i]);
for (int i = l; i < N; ++i) s[i]=(cor[i]==-1?r:cor[i]);
}
void exploreCave(int N) {
int s[N]={0}, cor[N]={0}, ans[N]={0};
for (int i = 0; i < N; ++i) s[i]=0, cor[i]=ans[i]=-1;
for (int i = 1; i <= N; ++i) {
setPrefix(N, 0, 0, s, cor);
int l=0, r=N, cor[i-1]=(tryCombination(s)==i);
while (l<r) {
int mid=(l+r)/2;
setPrefix(N, mid, cor[i-1], s, cor);
int t=tryCombination(s);
if (t==i) l=mid+1;
else r=mid;
} ans[i]=r;
} answer(cor, ans);
}