#include "koala.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100;
int moi[MAX_N], adverse[MAX_N], won[MAX_N];
void play() {
playRound(moi, adverse);
for (int i = 0; i < MAX_N; ++i) {
won[i] = (adverse[i] > moi[i]);
}
}
void reset() {
memset(moi, 0, sizeof(moi));
memset(adverse, 0, sizeof(adverse));
memset(won, 0, sizeof(won));
}
int minValue(int N, int W) {
reset();
moi[0] = 1;
play();
for (int i = 0; i < N; ++i) {
if (!won[i]) {
return i;
}
}
}
int maxValue(int N, int W) {
reset();
vector<int> isCand(N, 1);
int cnt = N;
while (cnt > 1) {
reset();
int perPos = N/cnt;
for (int i = 0; i < N; ++i) {
if (isCand[i]) {
moi[i] = perPos;
}
}
play();
cnt = 0;
for (int i = 0; i < N; ++i) {
isCand[i] &= won[i];
cnt += isCand[i];
}
}
int argMax = 0;
while (!isCand[argMax]) ++argMax;
return argMax;
}
bool comp(int N, int W, int i, int j) { // P[i] < P[j]
if (i == j) return false;
if (W == 2*N) {
reset();
moi[i] = moi[j] = N;
play();
return won[j];
} else {
assert(W == N);
reset();
int lo = 1, hi = min(9, W/2);
while (lo <= hi) {
int mid = (lo+hi)/2;
reset();
moi[i] = moi[j] = mid;
play();
if (won[i] < won[j]) return true;
if (won[i] > won[j]) return false;
if (!won[i]) hi = mid-1;
else lo = mid+1;
}
}
}
int greaterValue(int N, int W) {
return (comp(N, W, 0, 1) ? 1 : 0);
}
void allValues(int N, int W, int *P) {
auto Merge = [&] (auto merge, vector<int> A) {
int sz = A.size();
if (sz <= 1) return A;
vector<int> L(A.begin(), A.begin() + sz/2), R(A.begin() + sz/2, A.end());
L = merge(merge, L);
R = merge(merge, R);
A.clear();
reverse(L.begin(), L.end());
reverse(R.begin(), R.end());
while (!L.empty() || !R.empty()) {
auto &take = (R.empty() || (!L.empty() && comp(N, W, L.back(), R.back()))) ? L : R;
A.push_back(take.back());
take.pop_back();
}
return A;
};
vector<int> order(N);
iota(order.begin(), order.end(), 0);
order = Merge(Merge, order);
for (int i = 0; i < N; ++i) {
P[order[i]] = i+1;
}
}
