Submission #1230190

#TimeUsernameProblemLanguageResultExecution timeMemory
1230190neisennFinding Routers (IOI20_routers)C++20
72.23 / 100
3 ms840 KiB
#include <iostream> #include <utility> #include <set> #include <vector> #include "routers.h" using namespace std; #define pb push_back std::vector<int> find_routers(int l, int n, int q) { cin >> l >> n >> q; vector<int> p; p.pb(0); set<pair<int, int>> s; for (int i = 1; i < n; i++){ int lo = p[i-1]+1; int hi; if (s.empty()) hi = l; else { auto it = s.lower_bound({i, -1}); if (it == s.end()) hi = l; else hi = (*it).second; } int ans = -1; bool ok = 0; while (lo <= hi){ int mid = (lo+hi); if (ok) mid /= 2; else mid /= 3; int ret = use_detector(mid); s.insert({ret, mid}); if (ret > i){ hi = mid-1; } else { ok = 1; if (ret == i){ hi = mid-1; } else { ans = mid; lo = mid+1; } } } int x; if (ans == -1) x = p[i-1]+1; else { ans -= p[i-1]; x = 2*ans+p[i-1]; } p.pb(x); } vector<int> ans; for (int i : p) ans.pb(i); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...