#include "koala.h"
#include<bits/stdc++.h>
using namespace std;
int B[105], R[105];
int minValue(int N, int W) {
B[0] = 1;
playRound(B, R);
if(R[0] == 2)for(int i = 0; i < N; i++)if(R[i] == 0)return i;
return 0;
}
vector<int> search_set = {1, 2, 3, 5, 8};
int maxValue(int N, int W) {
vector<int> vec = {1, 2, 4, 11};
vector<int> good(N);
iota(good.begin(), good.end(), 0);
for(auto v: vec){
fill(B, B + N, 0);
for(auto id: good)B[id] = v;
playRound(B, R);
good.clear();
for(int i = 0; i < N; i++)if(R[i] > v)good.push_back(i);
}
return good.back();
}
int greaterValue(int N, int W) {
int l = 0, r = search_set.size()-1;
while(l <= r){
int md = (l+r)>>1;
int mid = search_set[md];
B[0] = B[1] = mid;
playRound(B, R);
if (R[0] > mid and R[1] <= mid) return 0;
if (R[1] > mid and R[0] <= mid) return 1;
if(R[0] > mid && R[1] > mid)l = md + 1;
else r = md - 1;
}
return 0;
// k p0 <= sum (k+1)so dau tien < p1
}
int n;
// 1-3, 3-9, 6-18, 15-45, 36-100
int bound[9][2] = {
{0, 0},
{0, 4},
{2, 10},
{5, 19},
{9, 31},
{14, 46},
{20, 64},
{27, 85},
{35, 101}
};
int cbound[105][2];
int cnt[105][2];
bool recmp[105][105];
int ans[105];
bool cmp(int a, int b){
assert(a != b);
if(recmp[a][b])return 1;
if(recmp[b][a])return 0;
int la = max(cnt[a][0] - 1, cbound[a][0]), ra = min(100 - cnt[a][1], cbound[a][1]);
int lb = max(cnt[b][0] - 1, cbound[b][0]), rb = min(100 - cnt[b][1], cbound[b][1]);
if(la >= rb){
cnt[a][0]++;
cnt[b][1]++;
recmp[b][a] = 1;
cbound[a][0] = max(cbound[a][0], cbound[b][0]);
cbound[b][1] = min(cbound[b][1], cbound[a][1]);
return 0;
}
if(lb >= ra){
recmp[a][b] = 1;
cnt[b][0]++;
cnt[a][1]++;
cbound[b][0] = max(cbound[b][0], cbound[a][0]);
cbound[a][1] = min(cbound[a][1], cbound[b][1]);
return 1;
}
int l = -1, r = -1;
for(int i = 0; i < search_set.size(); i++){
if(bound[search_set[i]][0] >= min(ra, rb) || bound[search_set[i]][1] <= max(la, lb))continue;
if(l == -1)l = i;
r = i;
}
while(l <= r){
int md = (l+r)>>1;
int mid = search_set[md];
fill(B, B+n, 0);
B[a] = B[b] = mid;
playRound(B, R);
// cout << mid << " " << R[a] << " " << R[b] << endl;
if (R[a] > mid and R[b] <= mid) {
cnt[a][0]++;
cnt[b][1]++;
recmp[b][a] = 1;
cbound[a][0] = max(cbound[a][0], cbound[b][0]);
cbound[b][1] = min(cbound[b][1], cbound[a][1]);
return 0;
}
if (R[b] > mid and R[a] <= mid) {
cnt[b][0]++;
cnt[a][1]++;
recmp[a][b] = 1;
cbound[b][0] = max(cbound[b][0], cbound[a][0]);
cbound[a][1] = min(cbound[a][1], cbound[b][1]);
return 1;
}
if(R[a] > mid && R[b] > mid){
l = md + 1;
cbound[a][0] = max(cbound[a][0], bound[mid][1]);
cbound[b][0] = max(cbound[b][0], bound[mid][1]);
}
else {
r = md - 1;
cbound[a][1] = min(cbound[a][1], bound[mid][0]);
cbound[b][1] = min(cbound[b][1], bound[mid][0]);
}
}
assert(false);
return 0;
}
bool cmp_subtask_4(int a, int b){
fill(B, B+n, 0);
B[a] = B[b] = n;
playRound(B, R);
return R[a] < R[b];
}
mt19937 rng_lmao(69420);
void allValues(int N, int W, int *P) {
n = N;
if (W == 2*N) {
vector<int> vec(N);
iota(vec.begin(), vec.end(), 0);
stable_sort(vec.begin(), vec.end(), cmp_subtask_4);
for(int i = 0; i < N; i++)P[vec[i]] = i+1;
} else {
for(int i = 0; i < N; i++)cbound[i][1] = 101;
vector<int> vec(N);
iota(vec.begin(), vec.end(), 0);
shuffle(vec.begin(), vec.end(), rng_lmao);
stable_sort(vec.begin(), vec.end(), cmp);
for(int i = 0; i < N; i++)P[vec[i]] = i+1;
}
}
