#include "koala.h"
#include <bits/stdc++.h>
using namespace std;
const int N=105;
int A[N],B[N];
int minValue(int N, int W) {
// TODO: Implement Subtask 1 solution here.
// You may leave this function unmodified if you are not attempting this
// subtask.
A[0]=1;
for(int i=1;i<N;i++) A[i]=0;
playRound(A,B);
for(int i=0;i<N;i++) if(A[i]>=B[i]) return i;
return -1;
}
void Clear(int N, int val=0){ for(int i=0;i<N;i++) A[i]=val;}
int maxValue(int N, int W) {
// TODO: Implement Subtask 2 solution here.
// You may leave this function unmodified if you are not attempting this
// subtask.
vector<int> cand(N);
for(int i=0;i<N;i++) cand[i]=i;
while(cand.size()>1)
{
Clear(N);
int mx=0;while((mx+1)*(mx+2)/2<N) mx++;
int put=min(W/(int)cand.size(),mx-1);
for(int i:cand) A[i]=put;
playRound(A,B);
cand.clear();
for(int i=0;i<N;i++) if(A[i]>0 && B[i]>A[i]) cand.push_back(i);
}
return cand[0];
}
int greaterValue(int N, int W) {
// TODO: Implement Subtask 3 solution here.
// You may leave this function unmodified if you are not attempting this
// subtask.
int top=0,bot=1,mid;
while((top+1)*(top+2)/2<N) top++;
while(top>=bot)
{
mid=top+bot>>1;
Clear(N);
A[0]=A[1]=mid;
playRound(A,B);
if(B[0]>A[0] && B[1]>A[1]) bot=mid+1;
else if(B[0]<=A[0] && B[1]<=A[1]) top=mid-1;
else break;
}
if(A[0]<B[0]) return 0;
else return 1;
}
bool comp(int x, int y, int N, int W)
{
Clear(N);
A[x]=A[y]=W/2;
playRound(A,B);
if(A[x]<B[x]) return 0;
if(A[y]<B[y]) return 1;
}
bool comp2(int x, int y, int N, int W)
{
int top=0,bot=1,mid;
while((top+1)*(top+2)/2<N) top++;
while(top>=bot)
{
mid=top+bot>>1;
Clear(N);
A[x]=A[y]=mid;
playRound(A,B);
if(B[x]>A[x] && B[y]>A[y]) bot=mid+1;
else if(B[x]<=A[x] && B[y]<=A[y]) top=mid-1;
else break;
}
if(A[x]<B[x]) return 0;
else return 1;
}
int C[N],D[N];
void MergeSort(int l, int r, function<bool(int,int)> cmp)
{
if(l==r) return;
int mid=l+r>>1;
MergeSort(l,mid,cmp);
MergeSort(mid+1,r,cmp);
int i=l,j=mid+1,k=l;
while(i<=mid || j<=r)
{
if(i>mid) D[k++]=C[j++];
else if(j>r) D[k++]=C[i++];
else if(cmp(C[i],C[j])) D[k++]=C[i++];
else D[k++]=C[j++];
}
for(i=l;i<=r;i++) C[i]=D[i];
}
void QuickSort(int l, int r, function<bool(int,int)> cmp)
{
if(l>=r) return;
if(r-l<=4 && 0)
{
for(int i=l+1,j;i<=r;i++)
{
int tmp=C[i];
for(j=i-1;j>=l;j--)
{
if(cmp(tmp,C[j])) C[j+1]=C[j];
else break;
}
C[j+1]=tmp;
}
return;
}
int pivot=rand()%(r-l+1)+l;
swap(C[pivot],C[r]);
int i,j=l;
for(i=l;i<r;i++)
{
if(cmp(C[i],C[r])) swap(C[i],C[j++]);
}
QuickSort(l,j-1,cmp);
QuickSort(j,r,cmp);
}
void allValues(int N, int W, int *P) {
if (W == 2*N) {
// TODO: Implement Subtask 4 solution here.
// You may leave this block unmodified if you are not attempting this
// subtask.
for(int i=0;i<N;i++) C[i]=i;
MergeSort(0,N-1,[&](int x, int y){ return comp(x,y,N,W);});
for(int i=0;i<N;i++) P[C[i]]=i+1;
} else {
// TODO: Implement Subtask 5 solution here.
// You may leave this block unmodified if you are not attempting this
// subtask.
srand(time(0));
Clear(N,1);
playRound(A,B);
int j=0;
for(int i=0;i<N;i++) if(B[i]<=A[i]) C[j++]=i;
int h=j;
for(int i=0;i<N;i++) if(B[i]>A[i]) C[j++]=i;
Clear(N);
A[0]=1;
playRound(A,B);
int mn;
for(int i=0;i<N;i++) if(A[i]>=B[i]) mn=i;
for(int i=0;i<N;i++) if(C[i]==mn) swap(C[i],C[0]);
MergeSort(1,h-1,[&](int x, int y){ return comp2(x,y,N,W);});
MergeSort(h,N-1,[&](int x, int y){ return comp2(x,y,N,W);});
for(int i=0;i<N;i++) P[C[i]]=i+1;
}
}
