#include "koala.h"
#include <bits/stdc++.h>
using namespace std;
int B[120];
int R[120];
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.
B[0] = 1;
for (int i = 1; i < N; i++) {
B[i] = 0;
}
playRound(B, R);
for (int i = 0; i < N; i++) {
if (R[i] <= B[i]) {
return i;
}
}
return -1;
}
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.
int cnt = N;
for (int i = 0; i < N; i++) {
B[i] = 1;
}
while (cnt > 1) {
for (int i = 0; i < N; i++) {
if (B[i] == 1) {
B[i] = W / cnt;
}
}
playRound(B, R);
cnt = 0;
for (int i = 0; i < N; i++) {
B[i] = (B[i] > 0 && R[i] > B[i]);
cnt += B[i];
}
}
for (int i = 0; i < N; i++) {
if (B[i] == 1) {
return i;
}
}
return -1;
}
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.
vector<int> vals = {2, 4, 8};
for (auto x: vals) {
B[0] = x;
B[1] = x;
for (int i = 2; i < N; i++) {
B[i] = 0;
}
playRound(B, R);
if ((R[0] > B[0]) != (R[1] > B[1])) {
if (R[0] > B[0]) {
return 0;
}
else {
return 1;
}
}
else {
if (x == 2 && R[0] <= B[0]) {
return minValue(N, W) ^ 1;
}
}
}
return -1;
}
int order[120];
int split[120][120];
int res[120];
bool cmp(int x, int y) {
for (int i = 0; i < 100; i++) {
B[i] = 0;
}
B[x] = 100;
B[y] = 100;
playRound(B, R);
return R[x] < R[y];
}
void solve(vector<int> cand, int lt, int rt) {
if (lt == rt) {
res[cand[0]] = lt;
return;
}
int k = split[lt][rt];
for (int i = 0; i < 100; i++) {
B[i] = 0;
}
for (auto id: cand) {
B[id] = k;
}
playRound(B, R);
vector<int> left_cand;
vector<int> right_cand;
for (auto id: cand) {
if (R[id] > B[id]) {
right_cand.emplace_back(id);
}
else {
left_cand.emplace_back(id);
}
}
int sz = left_cand.size();
solve(left_cand, lt, lt + sz - 1);
solve(right_cand, lt + sz, rt);
}
int sum(int lt, int rt) {
return (lt + rt) * (rt - lt + 1) / 2;
}
int suf(int rt, int len) {
return sum(rt - len + 1, rt);
}
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.
for (int i = 0; i < N; i++) {
order[i] = i;
}
stable_sort(order, order + N, cmp);
for (int i = 0; i < N; i++) {
P[order[i]] = i + 1;
}
}
else {
// TODO: Implement Subtask 5 solution here.
// You may leave this block unmodified if you are not attempting this
// subtask.
for (int len = 1; len <= 100; len++) {
for (int i = 1; i + len <= 101; i++) {
int j = i + len - 1;
split[i][j] = -1;
for (int k = 1; k <= 100 / len; k++) {
int mx = -1;
bool ok = true;
for (int x = 0; x <= len && x * (k + 1) <= 100; x++) {
int rem = min(100 - len, 100 - x * (k + 1));
int cur = suf(j, x) + (rem <= 100 - j ? suf(100, rem) : sum(j + 1, 100) + suf(i - 1, rem - (100 - j)));
if (cur > mx) {
mx = cur;
ok = true;
}
if (cur == mx) {
ok &= (x > 0 && x < len && split[i][j - len] != -1 && split[j - len + 1][j]);
}
}
if (ok) {
split[i][j] = k;
break;
}
}
}
}
vector<int> cand(N);
for (int i = 0; i < N; i++) {
cand[i] = i;
}
solve(cand, 1, N);
for (int i = 0; i < N; i++) {
P[i] = res[i];
}
}
}
