#include <bits/stdc++.h>
#include "koala.h"
int minValue(int N, int W) {
int B[100] = {}, R[100] = {};
B[0] = 1;
playRound(B, R);
for (int i = 0; i < N; ++i) {
if (R[i] <= B[i]) {
return i;
}
}
assert(false);
return -1;
}
int maxValue(int N, int W) {
int B[100] = {}, R[100] = {};
std::vector<int> cand(N);
std::iota(cand.begin(), cand.end(), 0);
while (cand.size() > 1) {
std::fill(B, B + N, 0);
for (const auto x: cand) {
B[x] = W / cand.size();
}
playRound(B, R);
std::vector<int> next;
for (const auto x: cand) {
if (R[x] > B[x]) {
next.push_back(x);
}
}
cand = std::move(next);
}
return cand[0];
}
int greaterValue(int N, int W) {
int B[100] = {}, R[100] = {};
int low = 1, high = 9;
while (low != high) {
const auto md = (low + high) / 2;
B[0] = B[1] = md;
playRound(B, R);
if (R[0] > B[0] and R[1] > B[1]) {
low = md + 1;
continue;
}
if (R[0] <= B[0] and R[1] <= B[1]) {
high = md - 1;
continue;
}
return (R[0] > B[0] ? 0 : 1);
}
B[0] = B[1] = low;
playRound(B, R);
return (R[0] > B[0] ? 0 : 1);
}
void allValues(int N, int W, int *P) {
int B[100] = {}, R[100] = {};
if (W == 2 * N) {
const auto less = [&](const int i, const int j) {
B[i] = B[j] = W / 2;
playRound(B, R);
B[i] = B[j] = 0;
return R[j] > W / 2;
};
int order[100] = {};
std::iota(order, order + N, 0);
auto dfs = [&](auto&& dfs, const int l, const int r) -> void {
if (r - l == 1) return;
const auto m = (l + r) / 2;
dfs(dfs, l, m);
dfs(dfs, m, r);
std::inplace_merge(order + l, order + m, order + r, less);
};
dfs(dfs, 0, N);
for (int i = 0; i < N; ++i) {
P[order[i]] = i + 1;
}
} else {
auto dfs = [&](auto&& dfs, std::vector<int> vec, const int L) -> void {
if (vec.size() == 1) {
P[vec[0]] = L;
return;
}
const auto x = std::min<int>(std::sqrt(2 * L), W / vec.size());
std::fill(B, B + N, 0);
for (const auto i: vec) {
B[i] = x;
}
playRound(B, R);
std::vector<int> left, right;
for (const auto i: vec) {
(R[i] > B[i] ? right : left).push_back(i);
}
dfs(dfs, left, L);
dfs(dfs, right, L + left.size());
};
std::vector<int> vec(N);
std::iota(vec.begin(), vec.end(), 0);
dfs(dfs, vec, 1);
}
}
