#include "routers.h"
#include <vector>
#include <map>
std::vector<int> find_routers(int l, int n, int q) {
// Stores the final even positions of the routers
std::vector<int> router_positions;
router_positions.push_back(0); // Router 0 is always at position 0
// Cache for detector results to avoid redundant API calls
// Using a vector since l is the maximum coordinate
std::vector<int> query_cache(l + 1, -1);
auto get_closest_router = [&](int x) {
if (query_cache[x] == -1) {
query_cache[x] = use_detector(x);
}
return query_cache[x];
};
for (int i = 1; i < n; i++) {
int prev_pos = router_positions[i - 1];
// Binary search to find the "boundary" where the detector
// stops returning (i-1) and starts returning (i) or higher.
int low = prev_pos + 1;
int high = l;
int boundary_midpoint = prev_pos;
while (low <= high) {
int mid = low + (high - low) / 2;
if (get_closest_router(mid) < i) {
// Still closer to the previous router(s)
boundary_midpoint = mid;
low = mid + 1;
} else {
// Reached the influence of the current router i
high = mid - 1;
}
}
// The boundary X is the midpoint between Router(i-1) and Router(i).
// X = (P[i-1] + P[i]) / 2 => P[i] = 2X - P[i-1]
int current_router_pos = 2 * boundary_midpoint - prev_pos;
router_positions.push_back(current_router_pos);
}
return router_positions;
}
