#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 m_sort(vector<int>&order, int l, int r) {
if(l==r) return;
int m = (r-l+1)/2;
m_sort(order, l, l+m), m_sort(order, l+m+1, r);
vector<int>t1, t2;
for(int i=l; i<=l+m; ++i) t1.push_back(order[i]);
for(int i=l+m+1; i<=r; ++i) t2.push_back(order[i]);
reverse(t1.begin(), t1.end());
reverse(t2.begin(), t2.end());
int p = l;
while(!t1.empty() || !t2.empty()) {
if(t1.empty()) {
order[p] = t2.back();
t2.pop_back();
++p;
} else if(t2.empty()) {
order[p] = t1.back();
t1.pop_back();
++p;
} else {
if(cmp(t1.back(), t2.back())) {
order[p] = t1.back();
t1.pop_back();
++p;
} else {
order[p] = t2.back();
t2.pop_back();
++p;
}
}
}
}
void allValues(int N, int W, int *P) {
if (W == 2*N) {
vector<int>order(N);
iota(order.begin(), order.end(), 0);
m_sort(order, 0, N-1);
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);
}
}
