#include "koala.h"
#include<bits/stdc++.h>
using namespace std;
template<class T>bool maximize(T& a, T b){
if(a < b){
a = b;
return true;
}
return false;
}
const int lim = 105;
int n, w, tmp1[lim], tmp2[lim];
vector<int>play_round(vector<int>b){
for(int i = 0; i < n; i++){
tmp1[i] = b[i];
}
playRound(tmp1, tmp2);
for(int i = 0; i < n; i++){
b[i] = tmp2[i];
}
return b;
}
namespace sub1{
int solve(){
vector<int>b(n, 0);
b[0] = 1;
if((b = play_round(b))[0] < 2){
return 0;
}
return find(b.begin(), b.end(), 0) - b.begin();
}
}
int minValue(int _n, int _w){
n = _n;
w = _w;
return sub1::solve();
}
namespace sub2{
int solve(){
vector<int>p(n);
iota(p.begin(), p.end(), 0);
while(p.size() > 1){
int d = n / p.size();
vector<int>b(n, 0);
for(int& i : p){
b[i] = d;
}
b = play_round(b);
vector<int>np;
for(int& i : p){
if(b[i] > d){
np.push_back(i);
}
}
swap(p, np);
}
return p[0];
}
}
int maxValue(int _n, int _w){
n = _n;
w = _w;
return sub2::solve();
}
namespace sub3{
int solve(){
vector<int>ICR = {5, 2, 1};
if(n == 6){
ICR = {2, 1, 1};
}
for(int bit = 0, z = 0; bit < 3; bit++){
int nz = z + ICR[bit];
vector<int>b(n, 0);
b[0] = b[1] = nz;
b = play_round(b);
if(b[0] <= nz && b[1] > nz){
return 1;
}
if(b[0] > nz && b[1] <= nz){
return 0;
}
if(b[0] > nz && b[1] > nz){
z = nz;
}
else if(bit == 2 && n > 6){
ICR[bit - 1]++;
}
}
}
}
int greaterValue(int _n, int _w){
n = _n;
w = _w;
return sub3::solve();
}
namespace sub4{
vector<int>solve(){
vector<int>p(n), ans(n);
iota(p.begin(), p.end(), 0);
stable_sort(p.begin(), p.end(), [&] (int i, int j){
vector<int>b(n, 0);
b[i] = b[j] = w >> 1;
b = play_round(b);
return b[j] > (w >> 1);
});
for(int i = 0; i < n; i++){
ans[p[i]] = i + 1;
}
return ans;
}
}
namespace sub5{
const int lim = 105;
bitset<lim>trace[lim];
bool check(int l, int r, int d){
vector<pair<int, int>>dp(n + 1, make_pair(0, 0));
for(int i = 1; i <= n; i++){
int cost = i < l || i > r ? 1 : d + 1;
trace[i].reset();
for(int j = n; j >= cost; j--){
if(maximize(dp[j], make_pair(dp[j - cost].first + i, dp[j - cost].second + 1))){
trace[i][j] = true;
}
}
}
int cnt = 0;
for(int i = n, j = n; i > 0; i--){
if(trace[i][j]){
if(l <= i && r >= i){
cnt++;
j -= d + 1;
}
else{
j--;
}
}
}
return cnt > 0 && cnt <= r - l;
}
vector<int>ans;
void play(vector<int>p, int l, int r){
if(p.size() == 1){
ans[p[0]] = l;
return;
}
int d = 1;
while(!check(l, r, d)){
d++;
}
vector<int>left, right, b(n, 0);
for(int& i : p){
b[i] = d;
}
b = play_round(b);
for(int& i : p){
if(b[i] > d){
right.push_back(i);
}
else{
left.push_back(i);
}
}
play(left, l, l + int(left.size()) - 1);
play(right, l + left.size(), r);
}
vector<int>solve(){
ans.resize(n);
iota(ans.begin(), ans.end(), 0);
play(ans, 1, n);
return ans;
}
}
void allValues(int _n, int _w, int *P){
n = _n;
vector<int>ans = (w = _w) == (n << 1) ? sub4::solve() : sub5::solve();
for(int i = 0; i < n; i++){
P[i] = ans[i];
}
}
