// And you curse yourself for things you never done
#include<bits/stdc++.h>
#include "koala.h"
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 110, mod = 1e9 + 7, inf = 1e9 + 10;
int minValue(int N, int W) {
int A[maxn], B[maxn];
memset(A, 0, sizeof A);
memset(B, 0, sizeof B);
A[0] = 1;
playRound(A, B);
if(B[0] <= 1)
return 0;
int ans = 0;
for(int i = 1; i < N; i++)
if(B[i] == 0)
ans = i;
return ans;
}
int maxValue(int N, int W) {
int SM[maxn];
vector<pii> v[maxn];
int h[maxn];
pii pr[maxn];
memset(SM, 0, sizeof SM);
memset(h, -1, sizeof h);
for(int i = 0; i < maxn; i++)
v[i].clear();
for(int i = 1; i <= N; i++)
SM[i] = SM[i-1] + i;
auto f = [&](int n, int cost, int top, int lim){
assert(top <= n);
int sm = 0, bst = 0;
for(int i = 0; i <= top; i++){
if(i * cost > lim)
break;
bst = max(bst, sm + SM[n-top] - SM[max(int(0), n-top-(lim - i*cost))]);
sm+= n-i;
}
sm = 0;
int bstid = -1;
for(int i = 0; i <= top; i++){
if(i * cost > lim)
break;
int num = sm + SM[n-top] - SM[max(int(0), n-top-(lim - i*cost))];
if(num == bst){
if(bstid == -1)
bstid = i;
if(bstid != i)
return -1;
}
sm+= n-i;
}
return bstid;
};
for(int top = 100; top >= 1; top--){
for(int cost = 2; top * (cost-1) <= 100; cost++){
int x = f(100, cost, top, 100);
if(x != -1)
v[top].PB({x, cost});
}
}
queue<int> q;
h[N] = 0;
q.push(N);
while(sz(q)){
int u = q.front();
q.pop();
for(pii p : v[u])
if(h[p.F] == -1)
pr[p.F] = {u, p.S}, h[p.F] = h[u] + 1, q.push(p.F);
}
vector<pii> tdo;
int tmp = 1;
while(tmp != N){
tdo.PB(pr[tmp]);
tmp = pr[tmp].F;
}
reverse(tdo.begin(), tdo.end());
vector<int> big;
for(int i = 0; i < N; i++){
big.PB(i);
}
int A[maxn], B[maxn];
bool inside[maxn];
for(pii p : tdo){
memset(A, 0, sizeof A);
memset(B, 0, sizeof B);
memset(inside, 0, sizeof inside);
for(int id : big)
A[id] = p.S-1, inside[id] = 1;
playRound(A, B);
big.clear();
for(int i = 0; i < N; i++){
if(inside[i] && B[i] >= p.S)
big.PB(i);
}
}
assert(sz(big) == 1);
return big[0];
}
bool comp(int a, int b){
int A[maxn], B[maxn];
int L = 1, R = 9;
while(true){
int d = (L+R) >> 1;
memset(A, 0, sizeof A);
memset(B, 0, sizeof B);
A[a] = d, A[b] = d;
playRound(A, B);
bool X = B[a] > d, Y = B[b] > d;
if(X ^ Y){
if(X)
return 0;
else
return 1;
}
if(X && Y)
L = d+1;
else
R = d-1;
}
assert(0);
}
int greaterValue(int N, int W) {
return comp(0, 1);
}
int magic[maxn][maxn];
void go(int l, int r, vector<int> vec, int *P){
int A[maxn], B[maxn];
if(r-l == 1){
P[vec.back()] = l;
return;
}
memset(A, 0, sizeof A);
for(int x : vec){
A[x] = magic[l][r];
}
playRound(A, B);
vector<int> v1, v2;
for(int i : vec){
if(A[i] >= B[i])
v1.PB(i);
else
v2.PB(i);
}
assert(!v1.empty() && !v2.empty());
go(l, l + sz(v1), v1, P);
go(l + sz(v1), r, v2, P);
}
void allValues(int N, int W, int *P) {
int SM[maxn];
SM[0] = 0;
for(int i = 1; i < maxn; i++)
SM[i] = SM[i-1] + i;
auto f = [&](int l, int r, int cost){
pii bst = {-1, 0};
int ret = -1;
for(int i = r; i >= l && (r-i) * cost <= W; i--){
pii p = {SM[r-1] - SM[i], r-i};
int rst = W - (r-i) * cost;
if(rst <= N - r + 1)
p.S+= rst, p.F+= SM[N] - SM[N - rst];
else
rst-= (N-r+1), p.S+= (N-r+1), p.F+= SM[N] - SM[r-1];
rst = min(rst, l-1);
p.S+= rst, p.F+= SM[l-1] - SM[l-1-rst];
pii _ = bst;
bst = max(bst, p);
if(_ != bst)
ret = i;
}
return ret;
};
for(int l = 1; l <= N; l++){
for(int r = l+2; r <= N + 1; r++){
magic[l][r] = -1;
for(int cst = 1; cst * (r-l) <= W; cst++){
int num = f(l, r, cst+1);
if(num == -1){
P[0] = l, P[1] = r, P[2] = cst;
return;
}
if(num != l && num != r){
magic[l][r] = cst;
break;
}
}
assert(magic[l][r] != -1);
}
}
vector<int> vec;
for(int i = 0; i < N; i++)
vec.PB(i);
go(1, N + 1, vec, P);
}
