#include "routers.h"
#include <bits/stdc++.h>
using namespace std;
map <int, int> dp;
int ask (int x) {
if (dp.count(x)) return dp[x];
return dp[x] = use_detector(x);
}
std::vector<int> find_routers(int l, int n, int q) {
dp.clear();
if (n == 2) {
int L = 1, R = l, ans = -1;
while (L <= R) {
int mid = (L + R) / 2;
if (ask(mid) == 0) {
L = mid + 1; ans = mid;
} else {
R = mid - 1;
}
}
return {0, 2 * ans};
}
vector <int> ret;
ret.push_back(0);
int B = 64;
for (int i = 1; i <= l; i += B) {
int d = ask(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 (ask(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;
}
