#include "koala.h"
#include <bits/stdc++.h>
using namespace std;
int n;
int B[110],R[110];
int minValue(int N, int W)
{
n=N;
fill_n(B,n,0);
B[0] = 1;
playRound(B,R);
if (R[0]<=1) return 0;
else for (int i=1; i<n; i++) if (R[i]==0)
return i;
}
int maxValue(int N, int W)
{
n=N;
vector <int> tmp;
for (int i=0; i<n; i++) tmp.push_back(i);
while (tmp.size()!=1)
{
int val = W / (tmp.size());
fill_n(B,n,0);
for (int i:tmp) B[i] = val;
playRound(B,R);
tmp.clear();
for (int i=0; i<n; i++) if (R[i]>val) tmp.push_back(i);
}
return tmp[0];
}
int greaterValue(int N, int W)
{
n=N;
fill_n(B,n,0);
int l=1; int r=min(9,W/2);
while (l<r)
{
int mid=(l+r)/2;
B[0]=B[1]=mid;
playRound(B,R);
if (R[0]>mid&&R[1]>mid) l=mid+1;
else if (R[0]<=mid&&R[1]<=mid) r=mid-1;
else return (R[0]<R[1]);
}
B[0]=B[1]=l;
playRound(B,R);
return (R[0]<R[1]);
}
bool comp(int u, int v, int W)
{
fill_n(B,n,0);
B[u]=B[v]=W;
playRound(B,R);
return R[v]>W;
}
vector <int> msort(vector <int> v, int lx, int rx, int W)
{
if (lx==rx) return v;
int mid=(lx+rx)/2;
vector <int> a,b;
a.insert(a.end(),v.begin(),v.begin()+(mid-lx+1));
b.insert(b.end(),v.begin()+(mid-lx+1),v.end());
a=msort(a,lx,mid,W);
b=msort(b,mid+1,rx,W);
vector <int> res;
int ita,itb;
ita=itb=0;
while (ita<a.size()&&itb<b.size())
{
if (comp(a[ita],b[itb],W)) res.push_back(a[ita++]);
else res.push_back(b[itb++]);
}
res.insert(res.end(),a.begin()+ita,a.end());
res.insert(res.end(),b.begin()+itb,b.end());
return res;
}
void sub4(int N, int W, int *P)
{
n=N;
vector <int> tmp;
for (int i=0; i<n; i++) tmp.push_back(i);
tmp=msort(tmp,0,n-1,W/2);
for (int i=0; i<n; i++) P[tmp[i]] = i+1;
}
void dnc(vector <int> v, int lx, int rx, int W, int *P)
{
if (lx>rx) return;
if (lx==rx)
{
P[v[0]]=lx+1;
return;
}
int mid=(lx+rx)/2;
int x = min(int(trunc(sqrt(2*(lx+1)))),W/(rx-lx+1));
fill_n(B,n,0);
for (int i:v) B[i]=x;
playRound(B,R);
vector <int> vl,vr;
for (int i:v) if (R[i]<=x) vl.push_back(i);
else vr.push_back(i);
dnc(vl,lx,lx+vl.size()-1,W,P);
dnc(vr,rx-vr.size()+1,rx,W,P);
}
void sub5(int N, int W, int *P)
{
n=N;
vector <int> tmp;
for (int i=0; i<n; i++) tmp.push_back(i);
dnc(tmp,0,n-1,W,P);
}
void allValues(int N, int W, int *P)
{
if (W==2*N) sub4(N,W,P);
else
sub5(N,W,P);
}
