Submission #599871

#TimeUsernameProblemLanguageResultExecution timeMemory
599871jophyyjhLost in the cycle (IOI19_cycle)C++14
100 / 100
1 ms288 KiB
/** * Simple. * * Steps needed: log_2(n) * Implementation 1 */ #include <bits/stdc++.h> #include "cycle.h" int n; int pos = 0; // treat our initial (unknown) starting room as room 0. Provides jumping with // absolute coordinate inline int absolute_jump(int k) { int steps = (k - pos + n) % n; pos = k; bool ans = jump(steps); // std::cerr << k << ' ' << ans << std::endl; return ans; } void escape(int _n) { n = _n; bool a = absolute_jump(0), b = absolute_jump(n / 2); assert(a || b); if (a && b) { if (absolute_jump(1)) absolute_jump(n / 2); else absolute_jump(0); return; } int left = 0, right = n / 2; if (b && !a) { std::swap(left, right); std::swap(a, b); } assert(a && !b); while (left != right) { int dist = (right - left + n) % n; int mid = left + (dist + 1) / 2; if (absolute_jump(mid)) left = (mid + n) % n; else right = (mid - 1 + n) % n; } absolute_jump(left); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...