제출 #339801

#제출 시각아이디문제언어결과실행 시간메모리
339801mihai145Finding Routers (IOI20_routers)C++14
96.67 / 100
2 ms384 KiB
#include "routers.h" using namespace std; int ans[1005]; void Solve(int searchL, int searchR, int routerL, int routerR) { if(searchL > searchR) return ; if(routerL > routerR) return ; int router = (routerL + routerR) / 2; int st = searchL, dr = searchR, sol = -1; while(st <= dr) { int mid = (st + dr) / 2; int idx = use_detector(mid); if(idx <= router) { sol = mid; st = mid + 1; } else { dr = mid - 1; } } ans[router] = sol; Solve(searchL, sol - 1, routerL, router - 1); Solve(sol + 1, searchR, router + 1, routerR); } std::vector<int> find_routers(int l, int n, int q) { Solve(0, l, 0, n - 2); std::vector<int> res; res.push_back(0); int lf = 0; for(int i = 0; i < n - 1; i++) { int pos = lf + 2 * (ans[i] - lf); res.push_back(pos); lf = pos; } return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...