# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1216961 | lukasuliashvili | 동굴 (IOI13_cave) | C++20 | 0 ms | 0 KiB |
#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
void exploreCave(int N) {
int s[N+5],fix[N+5],ans[N+5];
for (int i=0; i<N; i++) {
s[i]=0;
}
for (int i=0; i<N; i++) {
int l=0;
int r=N-1;
fix[i]=0;
while (l<=r) {
int mid = (l+r)/2;
for (int j=1; j<l; j++) {
s[j]=fix[i]^1;
}
for (int i=l; i<=mid; i++) {
s[j]=fix[i];
}
for (int i=mid+1; i<N; i++) {
s[j]=fix[i]^1;
}
int last=tryCombination(s);
if (last<=i){
fix[i]^=1;
l=mid+1;
}
else {
if (l==r) {
ans[i]=l;
}
r=mid-1;
}
}
}
answer(fix,ans);
}