#include "koala.h"
#include <bits/stdc++.h>
using namespace std;
int B[105], R[105];
int minValue(int N, int W) {
for(int i = 0; i < N; i++) B[i] = 1;
playRound(B, R);
for(int i = 0; i < N; i++) B[i] = 0;
for(int i = 0; i < N; i++){
if(R[i] > 1){
B[i] = 1;
break;
}
}
playRound(B, R);
for(int i = 0; i < N; i++){
if(R[i] <= B[i]) return i;
}
assert(0);
}
int maxValue(int N, int W) {
bool rem[105];
for(int i = 0; i < N; i++) rem[i] = true;
auto recalc = [&](){
int sum = 0;
for(int i = 0; i < N; i++) if(rem[i]) sum++;
for(int i = 0; i < N; i++){
if(rem[i]) B[i] = W / sum;
else B[i] = 0;
}
};
for(int t = 0; t < 4; t++){
recalc();
playRound(B, R);
for(int i = 0; i < N; i++){
if(R[i] <= B[i]) rem[i] = false;
}
}
for(int i = 0; i < N; i++){
if(rem[i]) return i;
}
assert(0);
}
bool comp(int x, int y){
vector<int> T = {1, 2, 3, 5, 8};
int l = 0, r = 4;
while(l <= r){
int mid = (l + r) / 2;
for(int i = 0; i < 100; i++) B[i] = 0;
B[x] = B[y] = T[mid];
playRound(B, R);
if(R[x] <= B[x] && R[y] <= B[y]) r = mid - 1;
else if(R[x] > B[x] && R[y] > B[y]) l = mid + 1;
else{
return R[x] <= B[x];
}
}
assert(0);
return 0;
}
bool comp2(int x, int y){
for(int i = 0; i < 100; i++) B[i] = 0;
B[x] = B[y] = 100;
playRound(B, R);
return R[x] <= B[x];
}
int greaterValue(int N, int W) {
if(comp(0, 1)) return 1;
else return 0;
}
vector<int> mergesort(int l, int r, const function<bool(int x, int y)>& cmp){
if(l == r) return {l};
vector<int> L = mergesort(l, (l + r) / 2, cmp), R = mergesort((l + r) / 2 + 1, r, cmp);
vector<int> ret;
int a = 0, b = 0;
while(a < L.size() || b < R.size()){
if(b == R.size() || (a != L.size() && cmp(L[a], R[b]))) ret.push_back(L[a++]);
else ret.push_back(R[b++]);
}
return ret;
}
void allValues(int N, int W, int *P) {
vector<int> ptr(N);
for(int i = 0; i < N; i++) ptr[i] = i;
if (W == 2*N) {
ptr = mergesort(0, N - 1, comp2);
}
else {
ptr = mergesort(0, N - 1, comp);
}
for(int i = 0; i < N; i++){
P[ptr[i]] = i + 1;
}
}
