#include "koala.h"
#include <bits/stdc++.h>
#ifdef LOCAL
#include "template/debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif
int minValue(int N, int W) {
int B[N], R[N];
for (int i = 0; i < N; i++) {
B[i] = 0;
}
B[0] = 1;
playRound(B, R);
for (int i = 0; i < N; i++) {
if (R[i] <= B[i]) {
return i;
}
}
}
int maxValue(int N, int W) {
int B[N], R[N];
for (int i = 0; i < N; i++) {
B[i] = 1;
}
playRound(B, R);
int candidate[N];
for (int i = 0; i < N; i++) {
if (R[i] > B[i]) {
candidate[i] = 1;
B[i] = 2;
} else {
candidate[i] = 0;
B[i] = 0;
}
}
playRound(B, R);
for (int i = 0; i < N; i++) {
if (R[i] > B[i]) {
if (candidate[i]) {
B[i] = 4;
} else {
B[i] = 0;
}
} else {
candidate[i] = 0;
B[i] = 0;
}
}
playRound(B, R);
for (int i = 0; i < N; i++) {
if (R[i] > B[i]) {
if (candidate[i]) {
B[i] = 11;
} else {
B[i] = 0;
}
} else {
candidate[i] = 0;
B[i] = 0;
}
}
playRound(B, R);
for (int i = 0; i < N; i++) {
if (R[i] > B[i] && candidate[i]) return i;
}
}
int greaterValue(int N, int W) {
int B[N], R[N];
for (int i = 0; i < N; i++) B[i] = 0;
int mb = 5;
B[0] = B[1] = mb;
playRound(B, R);
bool bought0 = R[0] > B[0];
bool bought1 = R[1] > B[1];
if (bought0 != bought1) return bought1;
if (bought0) {
mb = 8;
} else {
mb = 2;
}
B[0] = B[1] = mb;
playRound(B, R);
bought0 = R[0] > B[0];
bought1 = R[1] > B[1];
if (bought0 != bought1) return bought1;
if (bought0) {
mb = 3;
} else {
mb = 1;
}
B[0] = B[1] = mb;
playRound(B, R);
bought0 = R[0] > B[0];
bought1 = R[1] > B[1];
if (bought0 != bought1) return bought1;
assert(false);
}
void allValues(int N, int W, int *P) {
std::vector<int> ord(N);
std::iota(ord.begin(), ord.end(), 0);
if (W == 2 * N) {
int B[N]{}, R[N];
for (int i = 0; i < 100; i++) B[i] = 0;
auto compare = [&](int i, int j) -> bool {
B[i] = B[j] = W / 2;
playRound(B, R);
B[i] = B[j] = 0;
return R[j] > B[j];
};
std::function<void(std::vector<int>&)> merge_sort = [&](std::vector<int>& v) -> void {
if (v.size() == 1) return;
int mid = v.size() / 2;
std::vector<int> l(v.begin(), v.begin() + mid);
std::vector<int> r(v.begin() + mid, v.end());
merge_sort(l);
merge_sort(r);
std::merge(l.begin(), l.end(), r.begin(), r.end(), v.begin(), compare);
};
merge_sort(ord);
} else {
auto what_if_split = [&](int l, int r, int m) -> std::pair<int, int> {
int B[N]{};
int R[N];
for (int i = l; i < r; i++) {
B[i] = m;
}
std::vector<int> pp(N);
for (int i = 0; i < N; i++) {
pp[i] = i + 1;
}
int cache[2][205];
int num[2][205];
char taken[105][205];
for (int i = 0; i < 205; ++i) {
cache[1][i] = 0;
num[1][i] = 0;
}
for (int i = 0; i < N; ++i) {
int v = B[i] + 1;
int ii = i & 1;
int o = ii ^ 1;
for (int j = 0; j <= W; ++j) {
cache[ii][j] = cache[o][j];
num[ii][j] = num[o][j];
taken[i][j] = 0;
}
for (int j = W; j >= v; --j) {
int h = cache[o][j - v] + pp[i];
int hn = num[o][j - v] + 1;
if (h > cache[ii][j] || (h == cache[ii][j] && hn > num[ii][j])) {
cache[ii][j] = h;
num[ii][j] = hn;
taken[i][j] = 1;
} else {
taken[i][j] = 0;
}
}
}
int cur = W;
for (int i = N - 1; i >= 0; --i) {
R[i] = taken[i][cur] ? (B[i] + 1) : 0;
cur -= R[i];
}
int cnt_r = 0, cnt_l;
for (int i = l; i < r; i++) {
cnt_r += R[i] > B[i];
}
cnt_l = r - l - cnt_r;
return {cnt_l, cnt_r};
};
std::function<void(std::vector<int>&, int, int)> merge = [&](std::vector<int>& v, int l, int r) -> void {
dbg(v, l, r);
if (r - l == 1) return;
int ans = -1;
int lb = 1, rb = W / (r - l);
while (lb <= rb) {
int mb = (lb + rb) / 2;
auto [cl, cr] = what_if_split(l, r, mb);
dbg(mb, cl, cr);
if (cl && cr) {
ans = mb;
break;
} else {
if (cl) {
rb = mb - 1;
} else {
lb = mb + 1;
}
}
}
assert(ans != -1);
int B[N]{}, R[N];
for (int i = l; i < r; i++) {
B[v[i]] = ans;
}
playRound(B, R);
int j = l;
for (int i = l; i < r; i++) {
if (R[v[i]] <= B[v[i]]) {
std::swap(v[i], v[j]);
j++;
}
}
merge(v, l, j);
merge(v, j, r);
};
merge(ord, 0, N);
}
for (int i = 0; i < N; i++) {
P[ord[i]] = i + 1;
}
}
