#include "koala.h"
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
int B[100],R[100],N;
int minValue(int n,int w){
for(int i=0;i<n;i++){
B[i]=0;
R[i]=0;
}
B[0]=1;
playRound(B,R);
for(int i=0;i<n;i++){
if(R[i]==0){
return i;
}
}
}
int maxValue(int n,int w){
int tot=n;
int x=w/tot,res=0;
for(int i=0;i<n;i++){
B[i]=1;
}
while(tot!=1){
playRound(B,R);
tot=0;
for(int i=0;i<n;i++){
if(R[i]>x){
tot++;
}
B[i]=0;
}
int y=x;
x=w/tot;
for(int i = 0 ; i<n;i++){
if(R[i]>y){
B[i]=x;
res=i;
}
}
}
return res;
}
int greaterValue(int n,int w){
int l=1,r=13,mid;
while(l<=r){
mid=(l+r)/2;
for(int i=0;i<n;i++){
B[i]=0;
R[i]=0;
}
B[0]=B[1]=mid;
playRound(B,R);
if(R[0]>R[1]){
return 0;
}else if(R[1]>R[0]){
return 1;
}else if(R[1]>mid){
l=mid+1;
}else{
r=mid-1;
}
}
return 0;
}
bool cmp(int x,int y){
for(int i=0;i<100;i++){
B[i]=0;
}
B[x]=B[y]=100;
playRound(B,R);
return R[x]<R[y];
}
vector<int>merge(vector<int>a,vector<int>b){
int j=0;
vector<int>c;
for(int i=0;i<a.size();i++){
if(j<b.size()){
if(cmp(a[i],b[j])){
c.pb(a[i]);
}else{
c.pb(b[j++]);
}
}else{
c.pb(a[i]);
}
}
while(j<b.size()){
c.pb(b[j++]);
}
return c;
}
vector<int> msort(int l, int r){
if(l==r){
return {l};
}
vector<int>a,b,c;
int mid=(l+r)/2;
a=msort(l,mid);
b=msort(mid+1,r);
c=merge(a,b);
return c;
}
void allValues(int n,int w,int* p){
vector<int>pos=msort(0,100);
msort(1,100);
for(int i=0;i<n;i++){
p[pos[i]]=i+1;
}
}
