#include "koala.h"
#include <bits/stdc++.h>
using namespace std;
using ll = int; using pii = pair<ll,ll>;
const int N = 100;
int qtrIdx[N];
int ans[N];
//playRound(a,b): int a[N] (you enter this in), int b[N] (it enters this in)
int minValue(int N1, int W) {
int a[N],b[N];
for (int i=0;i<N;i++) {
a[i]=1;
}
playRound(a,b);
ll xm = -1;
for (int i=0;i<N;i++) {
if (b[i]==2) {
xm = i;
}
}
for (int i=0;i<N;i++) {
a[i]=0;
if (i==xm) {
a[i]=1;
}
}
playRound(a,b);
for (int i=0;i<N;i++) {
if (b[i]==0) {
return i;
}
}
}
void prc() {
int a[N],b[N];
for (int i=0;i<N;i++) {
a[i]=1;
}
playRound(a,b);
int topHalf[N];
for (int i=0;i<N;i++) {
topHalf[i]=(b[i]==2);
a[i]=b[i];
}
playRound(a,b);
// int qtrIdx[N]; //quarter index:
//0 -> [1,25] (a=0,b=0)
//1 -> [26,50] (a=0,b=1)
//2 -> [51,75] (a=2,b=0)
//3 -> [76,100] (a=2,b=3)
for (int i=0;i<N;i++) {
if (a[i]==0 && b[i]==0) {
qtrIdx[i]=0;
}else if (a[i]==0 && b[i]==1) {
qtrIdx[i]=1;
}else if (a[i]==2 && b[i]==0) {
qtrIdx[i]=2;
}else if (a[i]==2 && b[i]==3) {
qtrIdx[i]=3;
}else {
assert(1==2);
}
}
}
int maxValue(int N1, int W) {
int a[N],b[N];
prc();
//put 3 in a: [76,100] -> b: put 50 into 1,2 and then remaining ones go into:
//[20,25] -> 6, [90,100] -> 4*11=44
//sumE = 1180
//[24,25] -> 2, [89,100] -> 4*12=48
//sumE = 1183
for (int i=0;i<N;i++) {
a[i]=3*(qtrIdx[i]==3);
}
playRound(a,b);
vector<int> v1,v2; //[76,88] and [89,100]
for (int i=0;i<N;i++) {
if (qtrIdx[i]==3) {
if (b[i]==4) {
v2.push_back(i);
} else {
v1.push_back(i);
}
}
}
assert(v2.size()==12);
for (int i=0;i<N;i++) {
a[i]=(qtrIdx[i]==2);
}
for (int t=0;t<7;t++) {
a[v1[t]]=1;
}
for (int t: v2) {
a[t]=3;
}
playRound(a,b);
//intervals: [1,25]->0, cost 1, [26,50] cost 25, [51,88] -> 32*1+6*0=32, cost 64+6=70, [89,100]->12*3=36, cost 4
for (int t: v2) {
if (b[t]==4) {
return t;
}
}
}
bool q(int x, int y) { //query p(x)<p(y)
//first: run 2 queries to partition into quarters
//if in different quarters -> done.
int a[N],b[N];
//prc();
if (qtrIdx[x]!=qtrIdx[y]) {
return (qtrIdx[x]<qtrIdx[y]);
}
//if in [76,100]:
//apply 1 to rest of [76,100] -> cost 2*23=46
//apply 3 to x,y -> cost 4 for "winner"
//range [19=76/4,25=100/4]
//apply 0 to [51,75] -> cost 1*25=25
//apply 0 to [26,50] -> cost 1*25=25
//apply 1 to [1,25]
if (qtrIdx[x]==3) {
for (ll i=0;i<N;i++) {
if (qtrIdx[i]==3) {
if (i==x || i==y) {
a[i]=3;
} else {
a[i]=1;
}
} else if (qtrIdx[i]==0) {
a[i]=1;
} else {
a[i]=0;
}
}
playRound(a,b);
return (b[x]<b[y]);
} else if (qtrIdx[x]==2) {
//if in [51,75]:
//apply 0 to rest of [51,75] -> cost 1*23=23
//apply 3 to x,y -> cost 4 for "winner"
//range [>12.5=51/4,~19=75/4]
//apply 1 to 23, 0 to 2 in rest of [76,100] -> cost 2*23+1*2=48
//apply 0 to [26,50] -> cost 1*25=25
//apply 1 to [1,25]
for (ll i=0;i<N;i++) {
if (qtrIdx[i]==2) {
if (i==x || i==y) {
a[i]=3;
} else {
a[i]=0;
}
} else if (qtrIdx[i]==0 || qtrIdx[i]==3) {
a[i]=1;
} else {
a[i]=0;
}
}
ll n2 = 0;
for (ll i=0;i<N;i++) {
if (qtrIdx[i]==3) {
if (n2<2) {
n2++;
a[i]=0;
}
}
}
playRound(a,b);
return (b[x]<b[y]);
} else if (qtrIdx[x]==1) {
//if in [26,50]:
//apply 1 to 24 (0 to 1) elements in [76,100] -> cost 51
//apply 0 to all of [51,75] -> cost 1*25=25
//apply 2 to x,y -> range [13,25], cost 3
//apply 0 to rest of [26,50] -> cost 1*23=23
//apply 2 to [1,25]
bool tf = 0;
for (ll i=0;i<N;i++) {
if (qtrIdx[i]==3) {
if (!tf) {
tf = 1; a[i]=0;
} else {
a[i]=1;
}
} else if (qtrIdx[i]==2) {
a[i]=0;
} else if (qtrIdx[i]==1) {
if (i==x || i==y) {
a[i]=2;
} else {
a[i]=0;
}
} else {
a[i]=2;
}
}
playRound(a,b);
return (b[x]<b[y]);
} else {
//if in [1,25]: leave just one "hole" open -> GG
bool tf = 0;
for (int i=0;i<N;i++) {
if (qtrIdx[i]==3) {
if (!tf) {
a[i]=0; tf=1;
} else {
a[i]=1;
}
} else if (qtrIdx[i]==1 || qtrIdx[i]==2) {
a[i]=0;
} else {
if (i==x || i==y) {
a[i]=0;
} else {
a[i]=1;
}
}
}
playRound(a,b);
return (b[x]<b[y]);
}
}
int greaterValue(int N, int W) { //return (P[x]<P[y])
prc();
prc();
return q(0,1);
}
void qstr(vector<ll> velem, ll x0) {
if (velem.size()==0) {
return;
} else if (velem.size()==1) {
ans[velem[0]]=x0; return;
}
mt19937 gen((long long)new char);
ll xp = velem[gen()%(velem.size())];
vector<ll> v1,v2;
for (ll x: velem) {
if (x==xp) {
continue;
}
bool is2 = q(xp,x);
if (is2) {
v2.push_back(x);
} else {
v1.push_back(x);
}
}
ans[xp]=x0+v1.size();
qstr(v1,x0);
qstr(v2,x0+v1.size()+1);
}
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.
} else {
prc();
vector<int> v1;
for (int i=0;i<N;i++) {
v1.push_back(i);
}
qstr(v1,0);
for (int i=0;i<N;i++) {
P[i]=ans[i];
}
}
}
