#include "koala.h"
#include<bits/stdc++.h>
using namespace std;
int lim[101];
int minValue(int N, int W) {
int B[N], R[N];
for(int i=0; i<N; ++i) {
B[i] = R[i] = 0;
}
B[0] = 1;
playRound(B, R);
if(R[0]<=1) {
return 0;
}
for(int i=1; i<N; ++i) {
if(R[i]==0) return i;
}
}
int maxValue(int N, int W) {
int B[N] = {0}, R[N] = {0};
set<int>s;
for(int i=0; i<N; ++i) {
s.insert(i);
}
while(s.size()>1) {
int val = W / s.size();
memset(B, 0, sizeof B);
memset(R, 0, sizeof R);
for(int x : s) {
B[x] = val;
}
playRound(B, R);
set<int>new_s;
for(int i=0; i<N; ++i) if(R[i]>B[i]) {
if(s.count(i)) new_s.insert(i);
}
s = new_s;
}
return *s.begin();
}
int greaterValue(int N, int W) {
int B[N] = {0}, R[N] = {0};
int l = 1, r = 13;
while(l<r) {
int mid = (l+r)/2;
B[0] = B[1] = mid;
playRound(B, R);
if(B[0]<R[0] && B[1]<R[1]) {
l = mid+1;
} else if(B[0]>=R[0] && B[1]>=R[1]) {
r = mid-1;
} else {
if(R[0]>B[0]) return 0;
return 1;
}
}
}
void solve(set<int>s, int *P, int mx, int N, int W) {
if(s.size()==1) {
P[*s.begin()] = mx;
return;
}
int B[N] = {0}, R[N] = {0};
int val = W / s.size();
val = min(val, lim[mx]);
for(int j : s) {
B[j] = val;
}
playRound(B, R);
set<int>bigger;
for(int j : s) {
if(R[j]>B[j]) {
bigger.insert(j);
}
}
for(int x : bigger) {
s.erase(x);
}
solve(bigger, P, mx, N, W);
mx -= bigger.size();
solve(s, P, mx, N, W);
}
bool cmp(int i, int j) {
int B[100] = {0}, R[100] = {0};
B[i] = B[j] = 100;
playRound(B, R);
if(R[i]>B[i]) return false;
return true;
}
void allValues(int N, int W, int *P) {
if (W == 2*N) {
vector<int>order(N);
iota(order.begin(), order.end(), 0);
stable_sort(order.begin(), order.end(), cmp);
for(int i=0; i<N; ++i) {
P[order[i]] = i+1;
}
} else {
int S = 0;
for(int i=1, cur=1; i<=N; ++i) {
if(i>S) S += cur, ++cur;
lim[i] = cur-2;
}
set<int>s;
for(int i=0; i<N; ++i) {
s.insert(i);
}
solve(s, P, N, N, W);
}
}
