이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "routers.h"
#include <unordered_map>
using namespace std;
int ans[1005];
unordered_map <int, int> memo;
int Get_Detector(int x) {
if(memo[x])
return memo[x];
return memo[x] = use_detector(x);
}
void Solve(int searchL, int searchR, int routerL, int routerR) {
if(searchL > searchR)
return ;
if(routerL > routerR)
return ;
if(searchL == searchR) {
ans[routerL] = searchL;
return ;
}
int router = (routerL + routerR) >> 1;
int st = searchL, dr = searchR, sol = -1;
int optL = dr, optR = st;
while(st <= dr) {
int mid = (st + dr) >> 1;
int idx = Get_Detector(mid);
if(idx <= router) {
sol = mid;
st = mid + 1;
} else {
dr = mid - 1;
}
if(idx == router) {
optL = min(optL, mid);
optR = max(optR, mid);
}
}
ans[router] = sol;
Solve(searchL, min(optL - 1, sol - 1), routerL, router - 1);
Solve(max(optR + 1, sol + 1), searchR, router + 1, routerR);
}
std::vector<int> find_routers(int l, int n, int q) {
Solve(1, 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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |