#include "koala.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e2 + 20;
int B[maxn];
int R[maxn];
int tr[maxn * 4];
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, int x, int y) {
// 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 v: vals) {
for (int i = 0; i < N; i++) {
B[i] = 0;
}
B[x] = v;
B[y] = v;
playRound(B, R);
if ((R[x] > B[x]) != (R[y] > B[y])) {
if (R[x] > B[x]) {
return x;
}
else {
return y;
}
}
else {
if (v == 2 && R[x] <= B[x]) {
return minValue(N, W) ^ (x ^ y);
}
}
}
return -1;
}
int greaterValue(int N, int W) {
return greaterValue(N, W, 0, 1);
}
int merge(int N, int W, int x, int y) {
if (x == -1) {
return y;
}
else if (y == -1) {
return x;
}
else {
return greaterValue(N, W, x, y);
}
}
void build(int N, int W, int id, int lt, int rt) {
if (lt == rt) {
tr[id] = lt - 1;
return;
}
int mt = (lt + rt) / 2;
build(N, W, id * 2, lt, mt);
build(N, W, id * 2 + 1, mt + 1, rt);
tr[id] = merge(N, W, tr[id * 2], tr[id * 2 + 1]);
}
void update(int N, int W, int id, int lt, int rt, int pos) {
if (lt == rt) {
tr[id] = -1;
return;
}
int mt = (lt + rt) / 2;
if (pos <= mt) {
update(N, W, id * 2, lt, mt, pos);
}
else {
update(N, W, id * 2 + 1, mt + 1, rt, pos);
}
tr[id] = merge(N, W, tr[id * 2], tr[id * 2 + 1]);
}
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.
} else {
// TODO: Implement Subtask 5 solution here.
// You may leave this block unmodified if you are not attempting this
// subtask.
build(N, W, 1, 1, N);
for (int i = N; i >= 1; i--) {
P[tr[1]] = i;
if (i == 1) {
break;
}
update(N, W, 1, 1, N, tr[1] + 1);
}
}
}
