# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1259578 | comgaTramAnh | Cave (IOI13_cave) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
/*int tryCombination(vector <int> S) {
for (int i = 0; i < (int) S.size(); i++) {
cout << S[i] << ' ';
}
cout << endl;
fflush(stdout);
int ret;
cin >> ret;
return ret;
}
void answer(vector <int> S, vector <int> D) {
cout << "Answer is" << endl;
for (int i = 0; i < (int) S.size(); i++) {
cout << S[i] << ' ';
}
cout << endl;
for (int i = 0; i < (int) D.size(); i++) {
cout << D[i] << ' ';
}
cout << endl;
} */
void exploreCave(int N) {
//vector <int> S(N), D(N);
vector <int> finalSwitch(N), finalS(N);
int S[N], D[N];
vector <bool> found(N);
for (int i = 0; i < N; i++) {
S[i] = 0;
D[i] = i;
found[i] = false;
}
for (int i = 0; i < N; i++) {
vector <int> tmp(N);
//int tmp[N];
for (int j = 0; j < N; j++) {
tmp[j] = S[j];
}
int door = tryCombination(tmp);
finalS[i] = 1;
if (door != i) {
finalS[i] = 0;
for (int j = 0; j < N; j++) {
if (found[j] == false) {
tmp[j] = 1 - tmp[j];
}
}
}
int lo = 0, hi = N - 1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
for (int j = lo; j <= mid; j++) {
if (found[j] == false) {
tmp[j] = 1 - tmp[j];
}
}
door = tryCombination(tmp);
if (door != i) {
finalSwitch[i] = mid;
hi = mid - 1;
for (int j = lo; j <= mid; j++) {
if (found[j] == false) {
tmp[j] = 1 - tmp[j];
}
}
}
else {
lo = mid + 1;
}
}
found[finalSwitch[i]] = true;
S[finalSwitch[i]] = finalS[i];
D[finalSwitch[i]] = i;
}
answer(S, D);
}