#include "koala.h"
#include <iostream>
#include <vector>
using namespace std;
int D[109], R[109];
void preset() {
for (int i = 0; i < 109; i++) { D[i] = 0; R[i] = 0; }
}
int minValue(int N, int W) {
preset(); D[0] = 1;
playRound(D, R);
for (int i = 0; i < N; i++) {
if (D[i] >= R[i]) return i;
}
return -1;
}
int maxValue(int N, int W) {
int P[4] = { 1, 2, 4, 11 };
vector<int>I; for (int i = 0; i < N; i++) I.push_back(i);
for (int i = 0; i < 4; i++) {
preset();
for (int j = 0; j < I.size(); j++) D[I[j]] = P[i];
playRound(D, R);
vector<int>II; for (int j = 0; j < I.size(); j++) { if (D[I[j]] < R[I[j]]) II.push_back(I[j]); }
I = II;
}
return I[0];
}
int solve_3(int N, int W, int P) {
preset();
D[0] = P; D[1] = P;
playRound(D, R);
int v1 = 0; if (D[0] < R[0]) v1 = 1;
int v2 = 0; if (D[1] < R[1]) v2 = 2;
return v1 + v2;
}
int greaterValue(int N, int W) {
int G = solve_3(N, W, 6);
if (G == 1 || G == 2) return G - 1;
if (G == 0) {
int G1 = solve_3(N, W, 1); if (G1 == 1 || G1 == 2) return G1 - 1;
int G2 = solve_3(N, W, 3); if (G2 == 1 || G2 == 2) return G2 - 1;
return -1;
}
if (G == 3) {
int G1 = solve_3(N, W, 9); if (G1 == 1 || G1 == 2) return G1 - 1;
return -1;
}
return -1;
}
bool isgreater(int N, int u, int v) {
preset();
D[u] = N; D[v] = N;
playRound(D, R);
if (R[v] > D[v]) {
// u < v
return true;
}
return false;
}
vector<int> mergesort(int N, vector<int>J) {
if (J.size() == 1) return J;
vector<int>J1, J2;
for (int i = 0; i < J.size() / 2; i++) J1.push_back(J[i]);
for (int i = J.size() / 2; i < J.size(); i++) J2.push_back(J[i]);
vector<int>K1 = mergesort(N, J1);
vector<int>K2 = mergesort(N, J2);
vector<int>L; int cl = 0, cr = 0;
while (cl + cr < (int)J.size()) {
if (cl == J1.size()) { L.push_back(K2[cr]); cr++; }
else if (cr == J2.size()) { L.push_back(K1[cl]); cl++; }
else {
bool t = isgreater(N, K1[cl], K2[cr]);
if (t == true) { L.push_back(K1[cl]); cl++; }
else { L.push_back(K2[cr]); cr++; }
}
}
return L;
}
void playRound_virtual(int N, int W, int *B, int *R) {
int i, j;
int S = 0; for (i = 0; i < N; ++i) S += B[i];
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] + (i + 1);
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 find_optimal(int N, int W, int cl, int cr) {
for (int i = 20; i >= 1; i--) {
if (i*(cr - cl + 1) > W) continue;
preset();
for (int j = cl; j <= cr; j++) D[j] = i;
playRound_virtual(N, W, D, R);
for (int j = cl; j <= cr; j++) {
if (D[j] < R[j]) return i;
}
}
return -1;
}
int FinalAnswer[100];
void solve(int N, int W, int cl, int cr, vector<int>vec) {
if (cl == cr) {
FinalAnswer[vec[0]] = cl + 1;
return;
}
int Z = find_optimal(N, W, cl, cr);
preset();
for (int j = 0; j < vec.size(); j++) D[vec[j]] = Z;
playRound(D, R);
vector<int>p1, p2;
for (int j = 0; j < vec.size(); j++) {
if (D[vec[j]] < R[vec[j]]) p2.push_back(vec[j]);
else p1.push_back(vec[j]);
}
solve(N, W, cl, cl + p1.size() - 1, p1);
solve(N, W, cl + p1.size(), cr, p2);
}
void allValues(int N, int W, int *P) {
if (W == 2*N) {
vector<int>K; for (int i = 0; i < N; i++) K.push_back(i);
vector<int>KK = mergesort(N, K);
for (int i = 0; i < N; i++) P[KK[i]] = i + 1;
}
else {
vector<int>I; for (int j = 0; j < N; j++) I.push_back(j);
solve(N, W, 0, N - 1, I);
for (int i = 0; i < N; i++) P[i] = FinalAnswer[i];
}
}
