// M
#include<bits/stdc++.h>
#include "koala.h"
using namespace std;
const int N = 109;
int B[N], R[N];
int minValue(int n, int W)
{
for (int i = 0; i < n; i ++)
B[i] = 1;
playRound(B, R);
int id = -1;
for (int i = 0; i < n; i ++)
if (R[i] > 1)
id = i;
assert(id != -1);
memset(B, 0, sizeof(B));
B[id] = 1;
playRound(B, R);
for (int i = 0; i < n; i ++)
if (!R[i])
return i;
}
int maxValue(int n, int W)
{
vector < int > Cnds;
for (int i = 0; i < n; i ++)
Cnds.push_back(i);
while (Cnds.size() > 1)
{
memset(B, 0, sizeof(B));
for (int a : Cnds)
B[a] = W / (int)Cnds.size();
playRound(B, R);
vector < int > TbC;
for (int a : Cnds)
if (R[a] > B[a])
TbC.push_back(a);
Cnds.swap(TbC);
TbC.clear();
}
assert(Cnds.size());
return Cnds[0];
}
int greaterValue(int n, int W)
{
int le = 0, ri = min(11, W / 2), md;
while (ri - le > 1)
{
md = (le + ri) >> 1;
memset(B, 0, sizeof(B));
B[0] = md; B[1] = md;
playRound(B, R);
int w0 = R[0] > md, w1 = R[1] > md;
if (w0 && !w1)
return 0;
if (w1 && !w0)
return 1;
if (w0 && w1)
le = md;
else
ri = md;
}
}
inline bool TestRound(int l, int r, int n, int W, int Cw)
{
if (Cw * (r - l + 1) > W)
return 0;
memset(B, 0, sizeof(B));
for (int i = 0; i < n; i ++)
B[i] = 0;
for (int i = l; i <= r; i ++)
B[i - 1] = Cw;
int ORGP[210];
for (int i = 0; i < n; i ++)
ORGP[i] = i + 1;
int i, j;
int cache[2][205];
int num[2][205];
char taken[105][205];
for (i=0;i<205;++i) {
cache[1][i] = 0;
num[1][i] = 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] + ORGP[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 Pkd = 0;
for (int i = l; i <= r; i ++)
if (R[i - 1] > B[i - 1])
Pkd ++;
if (Pkd == 0 || Pkd == r - l + 1)
return 0;
return 1;
}
void Solve(int l, int r, vector < int > A, int n, int W, int * P)
{
if (r < l)
return ;
if (l == r)
return void(P[A[0]] = l);
int w = W / n;
int Cw = W;
/*for (int i = r + 1; i <= n; i ++)
B[i] = w - 1, Cw -= B[i];*/
Cw /= (r - l + 1);
while (Cw && !TestRound(l, r, n, W, Cw))
Cw --;
assert(Cw);
memset(B, 0, sizeof(B));
for (int i : A)
B[i] = Cw;
playRound(B, R);
vector < int > Le, Ri;
for (int i : A)
{
if (R[i] > B[i])
Ri.push_back(i);
else
Le.push_back(i);
}
/*printf("Left, from %d to %d is : ", l, l + (int)Le.size() - 1);
for (int a : Le) printf("%d ", a); printf("\n");
printf("Right, from %d to %d is : ", l + (int)Le.size(), r);
for (int a : Ri) printf("%d ", a); printf("\n");*/
Solve(l, l + (int)Le.size() - 1, Le, n, W, P);
Solve(l + (int)Le.size(), r, Ri, n, W, P);
return ;
}
void allValues(int n, int W, int * P)
{
vector < int > A;
for (int i = 0; i < n; i ++)
A.push_back(i);
Solve(1, n, A, n, W, P);
}
