#include "koala.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef long long ll;
#define f first
#define s second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
const int MAXN = 105;
int play[MAXN];
int res[MAXN];
int tmp[MAXN];
int calls = 0;
void reset(int n) {
for (int i = 0; i< n; i++) {
play[i] = res[i] = 0;
}
}
void knapsack(int *B, int *R) {
int N = 100;
int W = 100;
int P[105];
for(int i = 0; i< N; i++) P[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] + P[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 retMin[105][105];
int retMax[105][105];
int ret[105];
void precompute_all() {
int n = 100;
for (int i = 0; i < n; i++) {
for (int j = i+1; j< n; j++) {
for (int k = 1; k<= 9; k++) {
reset(n);
play[i] = play[j] = k;
knapsack(play, res);
if (res[j] > k && res[i] <= k) {
retMin[i][j] = k;
break;
}
}
for (int k = 9; k >= 1; k--) {
reset(n);
play[i] = play[j] = k;
knapsack(play, res);
if (res[j] > k && res[i] <= k) {
retMax[i][j] = k;
break;
}
}
}
for (int j = i+2; j< n; j++) {
assert(retMin[i][i+1] == retMin[i][j]);
assert(retMax[i][i+1] <= retMax[i][j]);
}
}
for (int i = 0; i < n; i++) {
for (int j = i+1; j< n; j++) {
assert(retMin[i][i+1] <= retMin[i][j] && retMin[i][j] <= retMin[j-1][j]);
}
}
// for (int j = 1; j< n; j++) {
// for(int i = 0; i < j-1; i++) {
// assert(retMax[j-1][j] == retMax[i][j]);
// }
// }
}
void precompute() {
int n = 100;
for (int i = 0; i < n; i++) {
int j = i+1;
for (int k = 1; k<= 9; k++) {
reset(n);
play[i] = play[j] = k;
knapsack(play, res);
if (res[j] > k && res[i] <= k) {
ret[i] = k;
break;
}
}
}
}
int minValue(int N, int W) {
int n = N;
play[0] = 1;
playRound(play, res);
for (int i = 0; i < n; i++) {
if (res[i] == 0) {
return i;
}
}
reset(N);
play[1] = 1;
playRound(play, res);
for (int i = 0; i < n; i++) {
if (res[i] == 0) {
return i;
}
}
return -1;
}
int maxValue(int N, int W) {
int n = N;
for (int i = 0; i < n; i++) {
play[i] = 1;
}
playRound(play, res);
set <int> pots;
for (int i = 0; i< n; i++) {
if (res[i] > 0) {
pots.insert(i);
}
}
int times = 3;
while(times--) {
reset(N);
for (int x : pots) {
play[x] = W/(pots.size());
}
playRound(play, res);
set <int> newpots;
for (int i = 0; i< n; i++) {
if (res[i] > 0 && (pots.find(i) != pots.end())) {
newpots.insert(i);
}
}
pots = newpots;
}
return *(pots.begin());
}
int greaterValue(int N, int W) {
int n = N;
int lo = 1, hi = 9;
while (lo < hi) {
int mid = (lo+hi)/2;
reset(n);
play[0] = play[1] = mid;
for (int i = 2; i< n; i++) {
play[i] = 0;
}
playRound(play, res);
if (res[0] != res[1]) {
if (res[0] > res[1]) {
return 0;
} else {
return 1;
}
} else {
if (res[0] == 0) {
hi = mid-1;
} else {
lo = mid+1;
}
}
}
}
bool isLessThan(int x, int y, int N, int ori_lo, int ori_hi) {
int n = N;
int lo = ori_lo, hi = ori_hi;
while (lo <= hi) {
int mid = (lo+hi)/2;
reset(n);
play[x] = play[y] = mid;
playRound(play, res);
calls++;
if (res[x] != res[y]) {
if (res[x] > res[y]) {
return false;
} else {
return true;
}
} else {
if (res[x] == 0) {
hi = mid-1;
} else {
lo = mid+1;
}
}
}
assert(false);
}
void solveClassic(int *P, int L, int R, int N) {
if (L == R) {
return;
}
// printf("called %d %d\n", L, R);
int mid = (L+R)/2;
solveClassic(P, L, mid, N);
solveClassic(P, mid+1, R, N);
int i = L, j = mid+1;
int cur = L;
while(i <= mid && j <= R) {
int lo = ret[L]-1;
int hi = ret[R-1]+1;
// int lo = 1;
// int hi = 9;
// printf("%d %d\n", L, R);
if(isLessThan(P[i], P[j], N, lo, hi)) {
tmp[cur++] = P[i++];
} else {
tmp[cur++] = P[j++];
}
}
while(i <= mid) {
tmp[cur++] = P[i++];
}
while(j <= R) {
tmp[cur++] = P[j++];
}
for (int i = L; i<= R; i++) {
P[i] = tmp[i];
}
return;
}
void solve(int *P, int L, int R, int N, int W) {
if (L == R) {
return;
}
reset(N);
for (int i = L; i <= R; i++) {
play[P[i]] = W/(R-L+1);
}
playRound(play, res);
calls++;
vector<int> good, bad;
for (int i = L; i <= R; i++) {
if (res[P[i]] > 0) {
good.push_back(P[i]);
} else {
bad.push_back(P[i]);
}
}
if ((int) good.size() == 0 || (int) bad.size() == 0) {
// printf("%d %d can't go\n", L, R);
solveClassic(P, L, R, N);
return;
}
int cur = L;
for (int i = 0; i< (int) bad.size(); i++) {
P[cur++] = bad[i];
}
for (int i = 0; i< (int) good.size(); i++) {
P[cur++] = good[i];
}
solve(P, L, L+bad.size()-1, N, W);
// printf("solved %d %d: %d\n", L, L+bad.size()-1, calls);
solve(P, L+bad.size(), R, N, W);
// printf("solved %d %d: %d\n", L+bad.size(), R, calls);
}
void solve_subtask4(int N, int W, int *P) {
for (int i = 0; i < N; i++) {
P[i] = -1;
}
for (int i = 0; i < N; i++) {
set<int> pots;
for (int j = 0; j < N; j++) {
pots.insert(j);
}
while(true) {
int remcnt = 0;
for (int x : pots) {
if (P[x] == -1) {
remcnt++;
}
}
if (remcnt == 1) {
break;
}
reset(N);
for (int x : pots) {
if (P[x] == -1) {
play[x] = W/remcnt;
}
}
playRound(play, res);
set<int> newpots;
for (int j = 0; j< N; j++) {
if (res[j] > 0 && pots.find(j) != pots.end()) {
newpots.insert(j);
}
}
pots = newpots;
}
set<int> newpots;
for (int j: pots) {
if (P[j] == -1) {
newpots.insert(j);
}
}
pots = newpots;
P[*(pots.begin())] = N-i;
// printf("%d: %d\n", *pots.begin(), N-i);
}
}
void allValues(int N, int W, int *P) {
precompute();
for (int i = 0; i < N; i++) {
P[i] = i;
}
if (W == 2*N) {
solve_subtask4(N, W, P);
} else {
solve(P, 0, N-1, N, W);
for (int i = 0; i < N; i++) {
tmp[P[i]] = i;
}
for (int i = 0; i < N; i++) {
P[i] = tmp[i] + 1;
}
}
}
