Submission #1203416

#TimeUsernameProblemLanguageResultExecution timeMemory
1203416javkhlantugs0504Finding Routers (IOI20_routers)C++20
0 / 100
1 ms324 KiB
#include <vector> #include <algorithm> // Provided by the grader — DO NOT implement yourself! int use_detector(int x); // You must implement this std::vector<int> find_routers(int l, int n, int q) { std::vector<int> positions(n); positions[0] = 0; // router 0 is always at position 0 for (int i = 1; i < n; ++i) { // Binary search: leftmost position where use_detector(x) == i int lo = 0, hi = l, left = -1; while (lo <= hi) { int mid = (lo + hi) / 2; int res = use_detector(mid); if (res < i) { lo = mid + 1; } else { if (res == i) left = mid; hi = mid - 1; } } // Binary search: rightmost position where use_detector(x) == i lo = 0, hi = l; int right = -1; while (lo <= hi) { int mid = (lo + hi) / 2; int res = use_detector(mid); if (res > i) { hi = mid - 1; } else { if (res == i) right = mid; lo = mid + 1; } } // Estimate router position as the center of its range, rounded down to even int pos = ((left + right) / 2) & ~1; positions[i] = pos; } return positions; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...