# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1216815 | mariamp1 | Cave (IOI13_cave) | C++20 | 0 ms | 0 KiB |
#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
void exploreCave(int N) {
vector<int> S(N, 0), D(N, -1);
vector<bool> nnk(N, false);
for (int door = 0; door < N; door++) {
int result = tryCombination(S.data());
int state;
if (result == door || result == -1 || result > door)
state = 0;
else
state = 1;
int lo = 0, hi = N - 1, sw = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
vector<int> test = S;
for (int i = 0; i <= mid; i++) {
if (!locked[i])
test[i] = 1 - state;
}
for (int i = mid + 1; i < N; i++) {
if (!locked[i])
test[i] = state;
}
int res = tryCombination(test.data());
if (res == -1 || res > door) {
sw = mid;
hi = mid - 1;
} else {
lo = mid + 1;
}
}
S[sw] = state;
D[sw] = door;
nnk[sw] = true;
}
vector<int> finalD(N);
for (int i = 0; i < N; i++) {
finalD[D[i]] = i;
}
answer(S.data(), finalD.data());
}