#include <bits/stdc++.h>
#include "koala.h"
using namespace std;
//#define int long long
#define double long double
#define FOR(i,l,r,d) for(int i=(l);i<=(r);i+=(d))
#define szof(x) ((x).size())
#define vi vector<int>
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define mkp make_pair
const int INF = 2147483647;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;
int B[100];
int R[100];
int res[100];
int minValue(int N, int W) {
// TODO: Implement Subtask 1 solution here.
// You may leave this function unmodified if you are not attempting this
// subtask.
FOR(i,0,N-2,1){
B[i] = 0;
}
B[N-1] = 1;
playRound(B, R);
int ret = 0;
FOR(i,0,N-1,1){
if(R[i]<=B[i]){
ret = i;
}
}
return ret;
}
int maxValue(int N, int W) {
// TODO: Implement Subtask 2 solution here.
// You may leave this function unmodified if you are not attempting this
// subtask.
bool isMax[N];
/// Round 0: 100 -> 50
/// Round 1: 50 -> 25
/// Round 2: 25 -> 9
/// Round 3: 9 -> 1
int Maxstone[4] = {1, 2, 4, 11};
FOR(i,0,N-1,1){
isMax[i] = 1;
}
FOR(Round,0,3,1){
FOR(i,0,N-1,1){
if(isMax[i]==1){
B[i] = Maxstone[Round];
}
else{
B[i] = 0;
}
}
playRound(B, R);
FOR(i,0,N-1,1){
if(R[i]>B[i] and isMax[i]==1){
isMax[i] = 1;
}
else{
isMax[i] = 0;
}
}
}
FOR(i,0,N-1,1){
if(isMax[i]){
return i;
}
}
return 0;
}
int greaterValue(int N, int W) {
// TODO: Implement Subtask 3 solution here.
// You may leave this function unmodified if you are not attempting this
// subtask.
FOR(i,2,N-1,1){
B[i] = 0;
}
int lb=1, rb=14, mid;
while(lb<rb){
mid = (lb+rb) / 2;
B[0] = B[1] = mid;
playRound(B, R);
if(R[0]>B[0] and R[1]>B[1]){
lb = mid+1;
}
else if(R[0]<=B[0] and R[1]<=B[1]){
rb = mid-1;
}
else{
if(R[0]>B[0]){
return 0;
}
else{
return 1;
}
}
}
return 0;
}
bool cmp(int n1, int n2){
FOR(i,0,99,1){
B[i] = 0;
}
B[n1] = B[n2] = 100;
playRound(B, R);
return (R[n1]<R[n2]);
}
bool testPlayRound(int Min, int Max, int ccnt) {
//cerr<<"testPlayRound "<<Min<<"~"<<Max<<" ccnt="<<ccnt;
int i, j;
const int N=100, W=100;
int cache[2][205];
int num[2][205];
char taken[105][205];
int A[100];
for (i=0;i<205;++i) {
cache[1][i] = 0;
num[1][i] = 0;
}
FOR(i,0,99,1){
A[i] = i+1;
B[i] = (Min<=A[i] and A[i]<=Max) ? ccnt : 0;
}
for (i=0;i<N;++i) {
int v = B[i]+1;
int ii = i&1;
int o = ii^1;
for (j=0;j<=W;++j) {
cache[ii][j] = cache[o][j];
num[ii][j] = num[o][j];
taken[i][j] = 0;
}
for (j=W;j>=v;--j) {
int h = cache[o][j-v] + A[i];
int hn = num[o][j-v] + 1;
if (h > cache[ii][j] || (h == cache[ii][j] && hn > num[ii][j])) {
cache[ii][j] = h;
num[ii][j] = hn;
taken[i][j] = 1;
} else {
taken[i][j] = 0;
}
}
}
int cur = W;
for (i=N-1;i>=0;--i) {
R[i] = taken[i][cur] ? (B[i] + 1) : 0;
cur -= R[i];
}
int Maxcnt = 0;
FOR(i,Min-1,Max-1,1){
if(R[i] > B[i]){
Maxcnt++;
}
}
//cerr<<" Maxcnt="<<Maxcnt<<endl;
return (0<Maxcnt and Maxcnt<(Max-Min+1));
}
void split(bool *arr, int Min){
int cnt = 0;
FOR(i,0,99,1){
cnt += arr[i];
}
int Max = Min + cnt - 1;
//cerr<<"split "<<Min<<" ~ "<<Max<<endl;
if(cnt==1){
FOR(i,0,99,1){
if(arr[i]==1){
res[i] = Min;
}
}
return;
}
int ccnt = 1;
while(1){
if(testPlayRound(Min, Max, ccnt)){
bool arrmin[100], arrMax[100];
int mincnt=0, Maxcnt=0;
FOR(i,0,99,1){
if(arr[i]==1){
B[i] = ccnt;
}
else{
B[i] = 0;
}
}
playRound(B, R);
FOR(i,0,99,1){
if(arr[i]==1){
if(R[i] > B[i]){
arrMax[i] = 1;
arrmin[i] = 0;
Maxcnt++;
}
else{
arrMax[i] = 0;
arrmin[i] = 1;
mincnt++;
}
}
else{
arrMax[i] = 0;
arrmin[i] = 0;
}
}
split(arrmin, Min);
split(arrMax, Min + mincnt);
break;
}
ccnt++;
}
}
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.
int rk[100];
FOR(i,0,99,1){
rk[i] = i;
}
stable_sort(rk,rk+100,cmp);
FOR(i,0,99,1){
P[rk[i]] = i + 1;
}
} else {
// TODO: Implement Subtask 5 solution here.
// You may leave this block unmodified if you are not attempting this
// subtask.
bool arr[100];
FOR(i,0,99,1){
arr[i] = 1;
}
split(arr, 1);
FOR(i,0,99,1){
P[i] = res[i];
}
}
}
