#include "koala.h"
#include<bits/stdc++.h>
using namespace std;
#define v vector
v<int> query(v<int> q){
int R[100],B[100];
for(int i=0;i<q.size();i++) R[i]=q[i];
playRound(R,B);
v<int> res(q.size());
for(int i=0;i<q.size();i++)res[i]=B[i];
return res;
}
int minValue(int N, int W) {
v<int> q(N,1);
v<int> r = query(q);
q = v<int>(N,0);
for(int i=0;i<N;i++){
if(r[i]!=0){
q[i]=1;
break;
}
}
r = query(q);
for(int i=0; i<N; i++){
if(r[i]==0) return i;
}
}
int maxValue(int N, int W) {
v<int> poss;
for(int i=0;i<N;i++) poss.push_back(i);
while(poss.size()>1){
v<int> q(N,0);
for(int i:poss) q[i] = (W / (int)poss.size());
v<int> r=query(q);
v<int> nposs;
for(int i:poss){
if(r[i]>(W/(int)poss.size())) nposs.push_back(i);
}
poss = nposs;
}
return poss[0];
}
int greaterValueInd(int x, int y){
int l=1,r=9;
while(l<=r){
int m=(l+r)/2;
v<int> q(100,0);
q[x]=m;
q[y]=m;
v<int> rr = query(q);
if(rr[x]>m && rr[y]<=m) return 0;
else if(rr[y]>m && rr[x]<=m) return 1;
if(rr[x]<=m && rr[y]<=m) r=m-1;
else l=m+1;
}
}
int greaterValue(int N, int W) {
return greaterValueInd(0, 1);
}
int comp(int x, int y){
v<int> q(100, 0);
q[x] = 100;
q[y] = 100;
v<int> r = query(q);
if(r[x]==0) return 1;
else return 0;
}
void split(v<int> inds, int l, int r, int N, int W, int *P){
if(l==r){
P[inds[0]] = l;
return;
}
int w = min((int)sqrt(2*l), W/(r-l+1));
v<int> q(N,0);
for(int i:inds) q[i] = w;
v<int> rr = query(q);
v<int> le, gr;
for(int i:inds){
if(rr[i]>w) gr.push_back(i);
else le.push_back(i);
}
split(le, l, l+le.size()-1, N, W, P);
split(gr, l+le.size(), r, N, W, P);
}
void allValues(int N, int W, int *P) {
if (W == 2*N) {
v<int> ind;
for(int i=0; i<N; i++) ind.push_back(i);
stable_sort(ind.begin(), ind.end(), comp);
for(int i=0; i<N; i++) P[ind[i]] = i+1;
} else {
v<int> ind;
for(int i=0; i<N; i++) ind.push_back(i);
split(ind, 1, N, N, W, P);
}
}
