Submission #1217027

#TimeUsernameProblemLanguageResultExecution timeMemory
1217027lukasuliashviliCave (IOI13_cave)C++20
0 / 100
546 ms516 KiB
#include "cave.h" #include <vector> using namespace std; void exploreCave(int N) { vector<int> correctState(N, 0); // correct switch positions vector<int> switchToDoor(N, -1); // which door each switch controls vector<bool> visited(N, false); // switches that are already assigned vector<int> test(N, 0); // temporary array for testing for (int d = 0; d < N; ++d) { // Binary search to find which switch controls door d int lo = 0, hi = N - 1; int controllingSwitch = -1; while (lo <= hi) { int mid = (lo + hi) / 2; // Set unknown switches from lo to mid to 1, others to 0 for (int i = 0; i < N; ++i) { if (visited[i]) { test[i] = correctState[i]; // already known } else if (i >= lo && i <= mid) { test[i] = 1; } else { test[i] = 0; } } int res = tryCombination(test.data()); if (res == d || res == -1) { // One of [lo..mid] controls door d hi = mid - 1; } else { lo = mid + 1; } } controllingSwitch = lo; // Figure out the correct position for the controlling switch // Set it to 0 first for (int i = 0; i < N; ++i) test[i] = visited[i] ? correctState[i] : 0; test[controllingSwitch] = 0; int res0 = tryCombination(test.data()); correctState[controllingSwitch] = (res0 == d || res0 == -1) ? 0 : 1; switchToDoor[controllingSwitch] = d; visited[controllingSwitch] = true; } answer(correctState.data(), switchToDoor.data()); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...