#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 merge(int arr[], int p, int q, int r) {
// Create L ← A[p..q] and M ← A[q+1..r]
int n1 = q - p + 1;
int n2 = r - q;
int L[n1], M[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[p + i];
for (int j = 0; j < n2; j++)
M[j] = arr[q + 1 + j];
// Maintain current index of sub-arrays and main array
int i, j, k;
i = 0;
j = 0;
k = p;
// Until we reach either end of either L or M, pick larger among
// elements L and M and place them in the correct position at A[p..r]
while (i < n1 && j < n2) {
if (cmp(L[i], M[j])) {
arr[k] = L[i];
i++;
} else {
arr[k] = M[j];
j++;
}
k++;
}
// When we run out of elements in either L or M,
// pick up the remaining elements and put in A[p..r]
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = M[j];
j++;
k++;
}
}
// Divide the array into two subarrays, sort them and merge them
void mergeSort(int arr[], int l, int r) {
if (l < r) {
// m is the point where the array is divided into two subarrays
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
// Merge the sorted subarrays
merge(arr, l, m, r);
}
}
void allValues(int N, int W, int *P) {
if (W == 2*N) {
int order[N];
iota(order, order+N, 0);
mergeSort(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);
}
}
