#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];
void reset(int n) {
for (int i = 0; i< n; i++) {
play[i] = res[i] = 0;
}
}
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 = 14;
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 n = N;
int lo = 1, hi = 10;
while (lo < hi) {
int mid = (lo+hi)/2;
reset(n);
play[x] = play[y] = mid;
playRound(play, res);
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;
}
}
}
}
void solve(int *P, int L, int R, int N) {
if (L == R) {
return;
}
// printf("called %d %d\n", L, R);
int mid = (L+R)/2;
solve(P, L, mid, N);
solve(P, mid+1, R, N);
int i = L, j = mid+1;
int cur = L;
while(i <= mid && j <= R) {
if(isLessThan(P[i], P[j], N)) {
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_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) {
for (int i = 0; i < N; i++) {
P[i] = i;
}
if (W == 2*N) {
solve_subtask4(N, W, P);
} else {
int n = N;
reset(n);
for (int i = 0; i< n; i++) {
play[i] = 1;
}
playRound(play, res);
vector<int> lower1, lower2, lower;
vector<int> higher1, higher2, higher;
for(int i = 0; i< n; i++) {
if (res[i] == 0) {
lower.push_back(i);
} else {
higher.push_back(i);
}
}
reset(n);
for(int x : higher) {
play[x] = 2;
}
playRound(play, res);
for (int x : higher) {
if (res[x] > 0) {
higher2.push_back(x);
} else {
higher1.push_back(x);
}
}
for(int x : lower) {
if (res[x] > 0) {
lower2.push_back(x);
} else {
lower1.push_back(x);
}
}
int cur = 0;
for (int i = 0; i < (int) lower1.size(); i++) {
P[cur++] = lower1[i];
}
for (int i = 0; i < (int) lower2.size(); i++) {
P[cur++] = lower2[i];
}
for (int i = 0; i < (int) higher1.size(); i++) {
P[cur++] = higher1[i];
}
for (int i = 0; i < (int) higher2.size(); i++) {
P[cur++] = higher2[i];
}
int n1 = lower1.size(), n2 = lower2.size();
int N1 = higher1.size(), N2 = higher2.size();
solve(P, 0, n1-1, N);
solve(P, n1, n1+n2-1, N);
solve(P, n1+n2, n1+n2+N1-1, N);
solve(P, n1+n2+N1, N-1, N);
// solve(P, 0, N-1, N);
for (int i = 0; i < N; i++) {
tmp[P[i]] = i;
}
for (int i = 0; i < N; i++) {
P[i] = tmp[i] + 1;
}
}
}
