#include "koala.h"
#include <bits/stdc++.h>
int minValue(int N, int W) {
int B[100] = {}, R[100] = {};
B[0] = 1;
playRound(B, R);
for (int i = 1; i < N; ++i) {
if (R[i] == 0) {
return i;
}
}
return 0;
}
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) {
const int x = W / (int)cand.size();
for (const int i : cand) {
B[i] = x;
}
playRound(B, R);
std::vector<int> next;
for (const int i : cand) {
if (B[i] < R[i]) {
next.push_back(i);
}
B[i] = 0;
}
cand = std::move(next);
}
return cand[0];
}
int greaterValue(int N, int W) {
int B[100] = {}, R[100] = {};
const auto put_and_play = [&](const int x) {
B[0] = B[1] = x;
playRound(B, R);
return (B[0] < R[0]) + (B[1] < R[1]);
};
const int a = put_and_play(4);
if (a == 2) {
put_and_play(8);
} else if (a == 0) {
const int b = put_and_play(2);
if (b == 0) {
put_and_play(1);
}
}
return B[1] < R[1];
}
template <class F>
struct fixed_point : private F {
explicit fixed_point(F&& f) : F(std::forward<F>(f)) {}
template <class... Args>
decltype(auto) operator()(Args&&... args) const {
return F::operator()(*this, std::forward<Args>(args)...);
}
};
void allValues(int N, int W, int* P) {
int B[100] = {}, R[100] = {};
if (W == 2 * N) {
std::vector<int> ord(N);
std::iota(ord.begin(), ord.end(), 0);
fixed_point([&](auto&& dfs, const int l, const int r) -> void {
if (r - l == 1) {
return;
}
const int m = (l + r) / 2;
dfs(l, m);
dfs(m, r);
std::inplace_merge(ord.begin() + l, ord.begin() + m, ord.begin() + r,
[&](const int i, const int j) {
B[i] = B[j] = N;
playRound(B, R);
const bool ret = B[j] < R[j];
B[i] = B[j] = 0;
return ret;
});
})(0, N);
for (int i = 0; i < N; ++i) {
P[ord[i]] = i + 1;
}
} else {
std::vector<int> v(N);
std::iota(v.begin(), v.end(), 0);
fixed_point([&](auto&& dfs, const int l, std::vector<int> v) -> void {
if (v.size() == 1) {
P[v[0]] = l;
} else {
std::fill(B, B + N, 0);
const int w = std::min<int>(W / v.size(), std::sqrt(2 * l));
for (const int i : v) {
B[i] = w;
}
playRound(B, R);
std::vector<int> a, b;
for (const int i : v) {
(R[i] <= w ? a : b).push_back(i);
}
const int r = l + a.size();
dfs(l, std::move(a));
dfs(r, std::move(b));
}
})(1, std::move(v));
}
}
