#include "routers.h"
#include <unordered_map>
#include <random>
#include <time.h>
using namespace std;
int ans[1005];
unordered_map <int, int> memo;
int Get_Detector(int x) {
if(memo[x])
return memo[x];
memo[x] = use_detector(x);
return memo[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;
for(auto it : memo)
if(it.second <= router)
st = max(st, it.first);
else
dr = min(dr, it.first);
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) {
srand(time(0));
Solve(1, l - 1, 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;
}
