/**
* Well, if we naively do binary search per router, the score is ~70. After that, I
* was thinking if we can minimize the num. of queries by "re-using" information.
* use_detector() is clearly an increasing function, so
* use_detector(l) = use_detector(r)
* => use_detector(l) = use_detector(l+1) = ... = use_detector(r).
* This means we can do some form of caching, though its efficiency is unknown. Also,
* we do not know whether the grader is adaptive, but I'm pretty sure it can reduce
* the num. of queries significantly.
*
* Again, our task is to find the last point v with use_detector(v) = x (for each x).
* First, check a point every x points, and call these checked points "initial pts".
* Now, the "endpoints" we're finding must be between two initial points, so we can
* do binary jump for each one of them. The num of steps is l/x + n * log_2(x). The
* optimal x is 69, which yields at most 7557 steps (worst case). Good enough~
*
* Steps needed: ...
* Implementation 0.9 (Just for testing my way of cache)
*/
#include <bits/stdc++.h>
#include "routers.h"
typedef std::vector<int> vec;
std::map<int, int> cache1;
std::map<int, int, std::greater<int>> cache2;
int wrap_use(int i) {
auto it1 = cache1.lower_bound(i);
auto it2 = cache2.lower_bound(i);
if (it1 != cache1.end() && it2 != cache2.end()) {
if (it1->second == it2->second)
return it1->second;
}
int result = use_detector(i);
cache1[i] = cache2[i] = result;
return result;
}
vec find_routers(int l, int n, int q) {
cache1.clear();
cache2.clear();
vec ans = {0};
for (int i = 0; i < n - 1; i++) {
int prev = ans.back();
int a = prev, b = l;
while (a < b) {
int mid = (a + b + 1) / 2;
if (wrap_use(mid) == i)
a = mid;
else
b = mid - 1;
}
ans.push_back(2 * a - prev);
}
return ans;
}
