/**
* 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: n/x * log(x), x = 69 (~7500 steps, for [S4], but with caching)
* Implementation 1.6
*/
#include <bits/stdc++.h>
#include "routers.h"
typedef std::vector<int> vec;
const int X = 69;
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();
if (l == 100000 && n == 1000 && q == 20000) {
vec init_pt = {0}, init_ask = {0};
for (int i = X; i < l; i += X) {
init_pt.push_back(i);
init_ask.push_back(wrap_use(i));
}
init_pt.push_back(l);
init_ask.push_back(n - 1);
int m = init_pt.size();
vec midpoints;
for (int i = 0; i < m - 1; i++) {
int a = init_pt[i], b = init_pt[i + 1];
int left = init_ask[i], right = init_ask[i + 1];
while (left < right) {
int j1 = a, j2 = b;
while (j1 < j2) {
int mid = (j1 + j2 + 1) / 2;
if (wrap_use(mid) == left)
j1 = mid;
else
j2 = mid - 1;
}
midpoints.push_back(j1);
a = j1 + 1, left++;
}
}
vec ans = {0};
for (int mi : midpoints)
ans.push_back(2 * mi - ans.back());
return ans;
} else {
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;
}
}
