#include "koala.h"
#include <algorithm>
#include <vector>
std::vector<bool> query(const std::vector<int> &vec)
{
static int B[105], R[105];
int n = vec.size();
for (int i = 0; i < n; i++)
B[i] = vec[i];
playRound(B, R);
std::vector<bool> res(n);
for (int i = 0; i < n; i++)
res[i] = R[i] > B[i];
return res;
}
int minValue(int n, int m)
{
std::vector<int> vec(n);
vec[0] = 1;
auto res = query(vec);
for (int i = 0; i < n; i++)
{
if (!res[i])
return i;
}
return -1;
}
int maxValue(int n, int m)
{
std::vector<bool> in(n, true);
int cnt = n;
while (cnt > 1)
{
int w = m / cnt;
std::vector<int> vec(n);
for (int i = 0; i < n; i++)
vec[i] = in[i] ? w : 0;
auto res = query(vec);
cnt = 0;
for (int i = 0; i < n; i++)
{
in[i] = in[i] & res[i];
cnt += in[i];
}
}
for (int i = 0; i < n; i++)
{
if (in[i])
return i;
}
return -1;
}
int greaterValue(int n, int m)
{
std::vector<int> vec(n);
vec[0] = vec[1] = 4;
auto res = query(vec);
if (res[0] != res[1])
return res[1];
if (res[0])
{
vec[0] = vec[1] = 8;
return query(vec)[1];
}
vec[0] = vec[1] = 2;
res = query(vec);
if (res[0] != res[1])
return res[1];
vec[0] = vec[1] = 1;
return query(vec)[1];
}
int idx[105], val[105], n;
inline int calc_sum(int l, int r) { return (l + r) * (r - l + 1) / 2; }
int get_val(int l, int r)
{
int mn = 1, mx = n / (r - l + 1);
while (mn <= mx)
{
int mid = mn + mx >> 1, rem = 0, cur = r, left = 0;
for (int i = 0; i < n; i++)
{
if (i < l || i > r)
val[i] = 1;
else
{
val[i] = 0;
rem++;
}
}
while (rem > mid)
{
val[cur--] = mid + 1;
rem -= mid + 1;
}
val[cur] = rem;
while (true)
{
int goal = mid + 1 - val[cur];
if (left + goal > l || calc_sum(left + 1, left + goal) >= cur)
break;
for (int i = left; i < left + goal; i++)
{
val[i]--;
val[cur]++;
}
left += goal;
if (--cur < l)
break;
}
if (val[l] > mid)
mn = mid + 1;
else if (val[r] <= mid)
mx = mid - 1;
else
return mid;
}
throw;
}
void solve(int l, int r, const std::vector<int> &vec)
{
if (l == r)
{
idx[l] = vec[0];
return;
}
int w = get_val(l, r);
std::vector<int> qry(n);
for (int i = 0; i < n; i++)
qry[i] = std::binary_search(vec.begin(), vec.end(), i) ? w : 0;
auto res = query(qry);
std::vector<int> vec_l, vec_r;
for (int u : vec)
(res[u] ? vec_r : vec_l).push_back(u);
solve(l, r - vec_r.size(), vec_l);
solve(r - vec_r.size() + 1, r, vec_r);
}
void allValues(int _n, int m, int *arr)
{
n = _n;
std::vector<int> seq(n);
for (int i = 0; i < n; i++)
seq[i] = i;
if (m == n)
{
solve(0, n - 1, seq);
for (int i = 0; i < n; i++)
arr[idx[i]] = i + 1;
return;
}
std::stable_sort(seq.begin(), seq.end(), [&] (int x, int y)
{
std::vector<int> vec(n, 0);
vec[x] = vec[y] = n;
return (bool)query(vec)[y];
});
for (int i = 0; i < n; i++)
arr[seq[i]] = i + 1;
}
