I was solving the problem Finding Routers in the practice session of APIO 2025. I intuited (guessed) the following solution.

#include "routers.h"
#include <algorithm>

void search(int lpos, int rpos, int lrout, int rrout, std::vector<int>& last){
	if (rrout == lrout + 1){
		last[lrout] = std::max(last[lrout], rpos - 1);
		return;
	}
	if (rpos == lpos + 1){
		last[lrout] = std::max(last[lrout], lpos);
		return;
	}
	int mpos = (lpos + rpos) / 2;
	int mrout = use_detector(mpos);
	search(lpos, mpos, lrout, mrout + 1, last);
	search(mpos, rpos, mrout, rrout, last);
}

std::vector<int> find_routers(int l, int n, int q) {
	std::vector<int> last(n);
	search(0, l + 1, 0, n, last);
	std::vector<int> a(n);
	for (int i = 1; i < n; ++i)
		a[i] = 2 * last[i - 1] - a[i - 1];
	return a;
}

It gives the full 100 points but I have no proof of its correctness. It has an obvious $$$n\log_2{l}$$$ upper bound on the number of use_detector calls. This accounts for the first 3 subtasks. I think this bound can be further improved to $$$2n\log_2(\frac{l}{2n})$$$. However, none of these bounds explain why it can solve subtask 4 within $$$7500$$$ queries.

I found this blog post but the commentor also had no proof of his solution. I also found this solution which caches the queries. I think (not sure) it asks the same queries as my solution. It might be easier to reason about.