Submission #1221161

#TimeUsernameProblemLanguageResultExecution timeMemory
1221161FaresSTHCave (IOI13_cave)C++20
0 / 100
40 ms324 KiB
#include "bits/stdc++.h" #include "cave.h" using namespace std; void exploreCave(int n) { vector<bool> v(n, false); vector<int> s(n, 0), d(n, 0); int in = tryCombination(s.data()); // initial combination score for (int i = 0; i < n; i++) { int l = 0, r = n - 1; while (l < r) { int m = (l + r) / 2; // Flip bits in s from l to m if not visited for (int j = l; j <= m; j++) { if (!v[j]) s[j] = 1 - s[j]; } int cur = tryCombination(s.data()); // Revert flip for (int j = l; j <= m; j++) { if (!v[j]) s[j] = 1 - s[j]; } if (in != cur) { r = m; } else { l = m + 1; } } // After binary search, flip s[l] if needed for (int j = l; j <= l; j++) { if (!v[j]) s[j] = 1 - s[j]; } d[i] = l; v[l] = true; in = tryCombination(s.data()); // update in after flip } answer(s.data(), d.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...