#include "koala.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100;
int B[MAXN], R[MAXN];
void Reset() {
for (int i = 0; i < MAXN; i++) {
B[i] = R[i] = 0;
}
}
int Compare(int a, int b) {
int lo = 1, hi = 9;
while (lo <= hi) {
int k = (lo + hi) / 2;
Reset();
B[a] = B[b] = k;
playRound(B, R);
bool pick[2] = {R[a] > k, R[b] > k};
if (pick[0] == pick[1]) {
if (pick[0]) {
hi = k - 1;
} else {
lo = k + 1;
}
} else {
if (pick[0]) {
return 0;
} else {
return 1;
}
}
}
return 0;
}
int minValue(int N, int W) {
Reset();
B[0] = 1;
playRound(B, R);
for (int i = 0; i < N; i++) {
if (R[i] == 0) {
return i;
}
}
return 0;
}
int maxValue(int N, int W) {
vector<int> large(N);
iota(begin(large), end(large), 0);
while (large.size() > 1) {
int k = min(9, W / (int) large.size());
Reset();
for (auto i : large) {
B[i] = k;
}
playRound(B, R);
large.clear();
for (int i = 0; i < N; i++) {
if (R[i] > k) {
large.emplace_back(i);
}
}
}
return large[0];
}
int greaterValue(int N, int W) {
return Compare(0, 1);
}
void Solve(int N, int W, int *P, vector<int> v, int l, int r) {
if (l > r) return;
if (l == r) return void(P[v[0]] = l);
int k = min({(int) sqrt(2 * l), W / (r - l + 1), 8});
Reset();
for (auto i : v) {
B[i] = k;
}
playRound(B, R);
vector<int> ls, gr;
for (auto i : v) {
if (R[i] > k) {
gr.emplace_back(i);
} else {
ls.emplace_back(i);
}
}
Solve(N, W, P, ls, l, l + int(ls.size()) - 1);
Solve(N, W, P, gr, r - int(gr.size()) + 1, r);
}
void allValues(int N, int W, int *P) {
if (W == 2 * N) {
vector<int> v(N);
iota(begin(v), end(v), 0);
stable_sort(begin(v), end(v), [&](int a, int b) { return Compare(a, b); });
for (int i = 0; i < N; i++) {
P[v[i]] = i + 1;
}
} else {
vector<int> v(N);
iota(begin(v), end(v), 0);
return Solve(N, W, P, v, 1, N);
}
}
