#include "koala.h"
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
int B[100],R[100],N100,W1200;
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];
}
bool cmp1(int x,int y){
int l=1,r=13,mid;
while(l<=r) {
mid = (l + r) / 2;
for (int i = 0; i < 100; i++) {
B[i] = 0;
R[i] = 0;
}
B[x] = B[y] = mid;
playRound(B, R);
if (R[x] > R[y]) {
return y;
} else if (R[y] > R[x]) {
return x;
} else if (R[x] > mid) {
l = mid + 1;
} else {
r = mid - 1;
}
}
}
vector<int>merge(vector<int>a,vector<int>b){
int j=0,i=0;
vector<int>c;
while(j<b.size() && i<a.size()){
if(W1200>N100){
if(cmp(a[i],b[j])){
c.pb(a[i++]);
}else{
c.pb(b[j++]);
}
}else{
if(cmp1(a[i],b[j])){
c.pb(a[i++]);
}else{
c.pb(b[j++]);
}
}
}
while(j<b.size()){
c.pb(b[j++]);
}
while(i<a.size()){
c.pb(a[i++]);
}
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){
N100=n;W1200=w;
vector<int>pos=msort(0,99);
for(int i=0;i<n;i++){
p[pos[i]]=i+1;
}
}
