#include <bits/stdc++.h>
#include "koala.h"
using namespace std;
int B[100], R[100], N, W;
int minValue(int N, int W) {
B[0] = 1;
playRound(B, R);
for(int i = 0; i < N; ++i)
if(!R[i]) return i;
return -1;
}
int maxValue(int N, int W) {
vector<int> L;
for(int i = 0; i < N; ++i)
L.push_back(i);
while(L.size() > 1) {
int t = W / L.size();
for(int i = 0; i < N; ++i)
B[i] = R[i] = 0;
for(int i : L) B[i] = t;
playRound(B, R);
L.clear();
for(int i = 0; i < N; ++i) {
if(R[i] > t) {
L.push_back(i);
}
}
}
return L[0];
}
bool compare(int i, int j) {
int lo = 1, hi = min(W / 2, 8);
for(int i = 0; i < N; ++i) B[i] = 0;
while(lo <= hi) {
int mid = lo + hi >> 1;
B[i] = B[j] = mid;
playRound(B, R);
bool z = R[i] > B[i];
bool o = R[j] > B[j];
if(z == o) {
if(z) lo = mid + 1;
else hi = mid - 1;
} else {
return z ? 0 : 1;
}
}
}
int greaterValue(int _N, int _W) {
N = _N; W = _W;
return compare(0, 1);
}
int Q[100];
void sort(vector<int> &a, int l, int r) {
if(l == r) {
Q[l] = a[0];
return;
}
int t = W / a.size();
memset(B, 0, sizeof B);
for(int i : a) B[i] = t;
playRound(B, R);
vector<int> big, small;
for(int i : a) {
if(R[i] > t) big.push_back(i);
else small.push_back(i);
}
if(big == a || small == a) {
sort(a.begin(), a.end(), compare);
for(int i = l; i <= r; i++) {
Q[i] = a[i - l];
}
return;
}
sort(small, l, l + small.size() - 1);
sort(big, r - big.size() + 1, r);
}
void allValues(int _N, int _W, int *P) {
N = _N, W = _W;
vector<int> v;
for(int i = 0; i < N; ++i)
v.push_back(i);
sort(v, 0, N - 1);
for(int i = 0; i < N; ++i)
P[Q[i]] = i + 1;
}
