Submission #1193779

#TimeUsernameProblemLanguageResultExecution timeMemory
1193779chaeryeongFinding Routers (IOI20_routers)C++20
99.74 / 100
1 ms328 KiB
#include "routers.h" #include <bits/stdc++.h> using namespace std; std::vector<int> find_routers(int l, int n, int q) { if (n == 2) { int L = 1, R = l, ans = -1; while (L <= R) { int mid = (L + R) / 2; if (use_detector(mid) == 0) { L = mid + 1; ans = mid; } else { R = mid - 1; } } return {0, 2 * ans}; } vector <int> ret; ret.push_back(0); int B = 63; for (int i = 1; i <= l; i += B) { int d = use_detector(min(l, i + B - 1)); if (d == (int)ret.size() - 1) { continue; } int cur = max(i, ret.back()); while (cur <= min(l, i + B - 1)) { if (d == (int)ret.size() - 1) { break; } int L = cur, R = min(l, cur + B - 1), ans = -1; while (L <= R) { int mid = (L + R) / 2; if (mid < 0 || mid > l) exit(0); if (use_detector(mid) > (int)ret.size() - 1) { R = mid - 1; ans = mid; } else { L = mid + 1; } } if (ans == -1) { break; } int v = ans - ret.back() - 1; ret.push_back(ret.back() + 2 * v); cur = ret.back() + 1; } } return ret; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...