#include <bits/stdc++.h>
#include "koala.h"
using namespace std;
int minValue(int N, int W) {
int B[N]{}, R[N];
B[0] = 1;
playRound(B, R);
int pos = 0;
for(int i=1; i<N; i++)
if(R[i] == 0)
pos = i;
return pos;
}
int maxValue(int N, int W) {
int B[N]{}, R[N];
vector<int> psbl;
for(int i=0;i<N;i++)
psbl.push_back(i);
while(psbl.size() > 1){
int x = W / psbl.size();
fill(B, B+N, 0);
for(auto i : psbl)
B[i] = x;
playRound(B, R);
psbl.clear();
for(int i=0;i<N;i++){
if(R[i] > x)
psbl.push_back(i);
}
}
return psbl[0];
}
int a = 0, b = 1;
int greaterValue(int N, int W) {
int B[N]{}, R[N];
int l = 1, r = (sqrt(8*(W+W) + 1) - 1) / 4;
while(l<=r){
int mid = (l + r) >> 1;
B[a] = B[b] = mid;
playRound(B, R);
if(R[a] + R[b] == 0){
r = mid - 1;
} else if(R[a] == 0){
return 1;
} else if(R[b] == 0){
return 0;
} else {
l = mid + 1;
}
}
return 0;
}
vector<int> dac(int l, int r, int N, int W){
// cout<<l<<" "<<r<<" "<<N<<" "<<W<<"\n";
if(l > r)return {};
if(l == r)return {l};
int m = (l + r) >> 1;
auto L = dac(l, m, N, W);
auto R = dac(m+1, r, N, W);
vector<int> ret;
int i = 0, j = 0;
while(i < L.size() && j < R.size()){
a = L[i];
b = R[j];
bool B = greaterValue(N, W);
if(B){
ret.push_back(L[i++]);
} else {
ret.push_back(R[j++]);
}
}
while(i < L.size()){
ret.push_back(L[i++]);
}
while(j < R.size()){
ret.push_back(R[j++]);
}
return ret;
}
void allValues(int N, int W, int *P) {
if (W == 2*N) {
auto v = dac(0, N-1, N, W);
vector<int>pos(N);
int i = 0;
for(auto x : v)
pos[x] = i++;
for(int i=0;i<N;i++){
P[i] = pos[i];
}
} else {
// TODO: Implement Subtask 5 solution here.
// You may leave this block unmodified if you are not attempting this
// subtask.
}
}
