#include "routers.h"
#include <bits/stdc++.h>
using namespace std;
// subtask 1, 3
int g(std::vector<int> &memo, int p)
{
// cout << memo[p] << " xx-";
if (memo[p] == -1)
{
int k = use_detector(p);
memo[p] = k;
return k;
}
return memo[p];
}
void find_set(int n, int i, int l, int &idx, std::vector<int> &ans, std::vector<int> &memo)
{
int L = 0, R = l, M = (L + R) / 2;
while (L < R)
{
M = (L + R) / 2;
int lbl = g(memo, M);
// cout << L << " " << R << " " << M << " " << "\n";
if (lbl < i)
{
L = M + 1;
}
else
{
R = M;
}
}
idx = idx + 2 * (L - 1 - idx);
ans[i] = idx;
}
std::vector<int> find_routers(int l, int n, int q)
{
int idx = use_detector(0);
std::vector<int> memo(l + 1, -1);
std::vector<int> ans(n, l);
ans[0] = idx;
for (int i = 1; i < n; i++)
{
find_set(n, i, l, idx, ans, memo);
// find_set(n, n - i, idx, ans);
}
// for (int x : ans)
// {
// cout << x << " ";
// }
// for (int i = 0; i < n; i++)
// {
// ans.push_back(0);
// }
// cout << (L - 1) << endl;
return ans;
}
// subtask 2
// std::vector<int> find_routers(int l, int n, int q)
// {
// std::vector<int> ans;
// int prev = 0;
// int idx = use_detector(0), h = 1;
// ans.push_back(idx);
// for (int i = 1; i <= l; i++)
// {
// int f = use_detector(i);
// if (f != prev)
// {
// idx = (2 * i - 2 - idx);
// ans.push_back(idx);
// prev = f;
// }
// }
// for (int x : ans)
// {
// cout << x << " ";
// }
// return ans;
// }
// std::vector<int> find_routers(int l, int n, int q)
// {
// std::vector<int> ans;
// int prev = 0;
// int idx = use_detector(0), h = 1;
// ans.push_back(idx);
// for (int i = 1; i <= l; i++)
// {
// int f = use_detector(i);
// if (f != prev)
// {
// idx = (2 * i - 2 - idx);
// ans.push_back(idx);
// prev = f;
// }
// }
// for (int x : ans)
// {
// cout << x << " ";
// }
// return ans;
// }
