#include "koala.h"
#include <bits/stdc++.h>
using namespace std;
const int nx=1e2+5;
int minValue(int N, int W) {
int qrs[nx], ans[nx];
for (int i=0; i<N; i++) qrs[i]=(i==0);
playRound(qrs, ans);
for (int i=1; i<N; i++) if (ans[i]==0) return i;
return 0;
}
int maxValue(int N, int W) {
int qrs[nx], ans[nx], per, t=4;
vector<int> idx, nidx;
for (int i=0; i<N;i ++) idx.push_back(i);
while (t--)
{
per=W/idx.size();
for (int i=0; i<N; i++) qrs[i]=0;
for (auto x:idx) qrs[x]=per;
playRound(qrs, ans);
for (int i=0; i<N; i++) if (qrs[i]>0&&ans[i]>qrs[i]) nidx.push_back(i);
idx=nidx;
nidx.clear();
}
return idx[0];
}
int solve(int x, int *qrs, int *ans, int a, int b)
{
qrs[a]=qrs[b]=x;
playRound(qrs, ans);
if (ans[a]<=qrs[a]&&ans[b]>qrs[b]) return -2;
if (ans[a]>qrs[a]&&ans[b]<=qrs[b]) return -1;
if (ans[a]<=qrs[a]||ans[b]<=qrs[b]) return 1;
return 0;
}
int greatervalue(int N, int W, int x, int y)
{
// 1 when first is greater
int qrs[nx], ans[nx];
for (int i=0; i<N; i++) qrs[i]=0;
int l=1, r=10;
while (l<r)
{
int md=(l+r)/2;
int tmp=solve(md, qrs, ans, x, y);
if (tmp==-1) return 1;
if (tmp==-2) return 0;
if (tmp) r=md-1;
else l=md+1;
}
solve(l, qrs, ans, x, y);
if (ans[x]>qrs[x]) return 1;
else return 0;
}
int greaterValue(int N, int W) {
return greatervalue(N, W, 1, 0);
}
int srt[nx], tmp[nx], n, w;
bool comparesub4(int i, int j)
{
int qrs[nx], ans[nx];
for (int k=0; k<n; k++) qrs[k]=0;
qrs[i]=qrs[j]=100;
playRound(qrs, ans);
if (ans[i]<=qrs[i]) return 1;
else return 0;
}
bool maincompare(int i, int j, int t)
{
if (!t) return comparesub4(i, j);
else return greatervalue(n, w, j, i);
}
void mergesort(int l, int r, int t)
{
if (l==r) return;
int md=(l+r)/2, idxl=l, idxr=md+1, idx=l;
mergesort(l, md, t);
mergesort(md+1, r, t);
while (idxl<=md||idxr<=r)
{
if (idxl>md) tmp[idx++]=srt[idxr++];
else if (idxr>r) tmp[idx++]=srt[idxl++];
else if (maincompare(srt[idxl], srt[idxr], t)) tmp[idx++]=srt[idxl++];
else tmp[idx++]=srt[idxr++];
}
for (int i=l; i<=r; i++) srt[i]=tmp[i]; //cout<<"debug "<<l<<' '<<r<<' '<<srt[i]<<'\n';
}
void allValues(int N, int W, int *P) {
n=N;
w=W;
for (int i=0; i<N; i++) srt[i]=i;
if (W >= 2*N) {
mergesort(0, N-1, 0);
} else {
mergesort(0, N-1, 1);
}
for (int i=0; i<N; i++) P[srt[i]]=i+1;
}
