Submission #381966

#TimeUsernameProblemLanguageResultExecution timeMemory
381966Aryan_RainaCave (IOI13_cave)C++14
0 / 100
2090 ms492 KiB
#include "cave.h" #include <bits/stdc++.h> using namespace std; void exploreCave(int N) { /* ... */ vector<int> bit(N, -1), sw(N, -1); auto bs = [&](int doorNo, int state) { int lo = 0, hi = N-1, mid; int tmp[N]; for (int i = 0; i < N; i++) tmp[i] = state; while (lo < hi) { mid = (lo + hi) >> 1; for (int i = lo; i <= mid; i++) tmp[i] = !state; int xx = tryCombination(tmp); if (xx == doorNo) { hi = mid; } else { for (int i = lo; i <= mid; i++) tmp[i] = state; lo = mid+1; } } return hi; }; while (true) { int ones[N], zeros[N]; bool done = true; for (int i = 0; i < N; i++) { if (bit[sw[i]] == 0) { ones[i] = 0; zeros[i] = 0; } else if (bit[sw[i]] == 1) { zeros[i] = 1; ones[i] = 1; } else ones[i] = 1, zeros[i] = 0, done = false; } if (!done) { int x = tryCombination(ones); int y = tryCombination(zeros); if (x == -1) x = N; if (y == -1) y = N; if (x < y) { for (int i = x; i < y; i++) if (bit[i] == -1) { bit[i] = 1; } } else if (y < x) { for (int i = y; i < x; i++) if (bit[i] == -1) { bit[i] = 0; } } } for (int i = 0; i < N; i++) if (bit[i] != -1) { sw[i] = bs(i, bit[i]); } for (int i = 0; i < N; i++) if (sw[i] == -1) { done = false; } if (done) { int ans1[N]; for (int i = 0; i < N; i++) ans1[i] = bit[i]; int ans2[N]; for (int i = 0; i < N; i++) ans2[sw[i]] = i; answer(ans1, ans2); return; } } }
#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...