#include "routers.h"
#include <vector>
std::vector<int> find_routers(int l, int n, int q) {
// router_pos[i] will store the coordinate of the i-th router
std::vector<int> router_pos;
router_pos.push_back(0); // Router 0 is always at position 0
// Cache to store results of use_detector(x)
// Using a vector of size l+1 initialized to -1 (not queried yet)
std::vector<int> cache(l + 1, -1);
// Helper lambda to handle queries with memoization
auto get_closest = [&](int x) {
if (cache[x] == -1) {
cache[x] = use_detector(x);
}
return cache[x];
};
// Find each router from 1 to n-1 sequentially
for (int i = 1; i < n; i++) {
int low = 0;
int high = l;
int last_pos_of_prev = 0;
// Binary search for the "midpoint" boundary
while (low <= high) {
int mid = low + (high - low) / 2;
if (get_closest(mid) < i) {
// mid is still closer to a previous router
last_pos_of_prev = mid;
low = mid + 1;
} else {
// mid is closer to router i or higher
high = mid - 1;
}
}
// The boundary X is the midpoint between router i-1 and i.
// X = (P[i-1] + P[i]) / 2 => P[i] = 2*X - P[i-1]
int current_pos = 2 * last_pos_of_prev - router_pos[i - 1];
router_pos.push_back(current_pos);
}
return router_pos;
}
