#include <bits/stdc++.h>
using namespace std;
#include "koala.h"
int R[105], B[105];
void __init__() { memset(R, 0, sizeof R); memset(B, 0, sizeof B); }
int minValue(int N, int W) {
__init__();
B[0] = 1;
playRound(B, R);
for (int i = 1; i < N; i++)
if (!R[i]) return i;
return 0;
}
int maxValue(int N, int W) {
vector<int> res(N);
iota(res.begin(), res.end(), 0);
while ((int) res.size() > 1) {
__init__();
for (auto i : res)
B[i] = W / res.size();
playRound(B, R);
int f = *max_element(R, R + N);
res.clear();
for (int i = 0; i < N; i++)
if (R[i] == f) res.push_back(i);
}
return res[0];
}
int greaterValue(int N, int W) {
int l = 0, r = sqrt(N * 2);
while (l <= r) {
int mid = (l + r) >> 1;
__init__();
B[0] = B[1] = mid;
playRound(B, R);
int c0 = R[0] > B[0], c1 = R[1] > B[1];
if (c0 ^ c1) {
if (c0) return 0;
if (c1) return 1;
}
if (c0) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return 0;
}
int dp[105][205], ct[105][205], need[105];
inline int get_p(int N, int W, int LL, int RR) {
for (int p = 1; p <= W; p++) {
memset(dp, 0, sizeof dp);
memset(ct, 0, sizeof ct);
fill(need + 1, need + N + 1, 1);
for (int i = LL; i <= RR; i++)
need[i] = p + 1;
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= W; j++) {
dp[i][j] = dp[i - 1][j];
ct[i][j] = ct[i - 1][j];
if (j >= need[i] && dp[i][j] < dp[i - 1][j - need[i]] + i) {
dp[i][j] = dp[i - 1][j - need[i]] + i;
ct[i][j] = ct[i - 1][j - need[i]] + (i <= RR && i >= LL);
}
}
}
if (ct[N][W] > 0 && ct[N][W] < RR - LL + 1)
return p;
}
return 0;
}
void solve(int LL, int RR, int W, int *P, vector<int> pos) {
if (LL == RR) {
assert((int) pos.size() == 1);
return P[pos[0]] = LL, (void) 0;
}
vector<int> lef, rig;
int f = get_p(W, W, LL, RR);
__init__();
for (int i : pos) B[i] = f;
playRound(B, R);
for (int i : pos) {
if (R[i] > B[i])
rig.push_back(i);
else
lef.push_back(i);
}
int mid = LL + lef.size();
solve(LL, mid - 1, W, P, lef), solve(mid, RR, W, P, rig);
}
void allValues(int N, int W, int *P) {
vector<int> pos(N);
iota(pos.begin(), pos.end(), 0);
if (W == 2*N) {
solve(1, N, W, P, pos);
} else {
solve(1, N, W, P, pos);
}
}
