#include <bits/stdc++.h>
#include "koala.h"
using namespace std;
int minValue(int N, int W) {
int b[N], r[N];
memset(b, 0, sizeof(b));
b[0] = 1;
playRound(b, r);
for(int i = 0; i < N; i++)
if (r[i] == 0)
return i;
return 0;
}
int maxValue(int N, int W) {
vector<int> candidates;
for(int i = 0; i < N; i++)
candidates.push_back(i);
while (candidates.size() > 1){
int b[N], r[N];
memset(b, 0, sizeof(b));
int c = min(12, W / (int) candidates.size());
for(int ind : candidates)
b[ind] = c;
playRound(b, r);
vector<int> nxt;
for(int i = 0; i < N; i++)
if (b[i] == c && r[i] > c)
nxt.push_back(i);
candidates = nxt;
}
return candidates.front();
}
int greaterValue(int N, int W) {
int val[6] = {1, 2, 4, 6, 7, 8};
int lo = 0, hi = 5;
while (lo <= hi){
int mid = (lo + hi) >> 1;
int b[N], r[N];
memset(b, 0, sizeof(b));
b[0] = b[1] = val[mid];
playRound(b, r);
if (r[0] > b[0] && r[1] <= b[1])
return 0;
else if (r[0] <= b[0] && r[1] > b[1])
return 1;
else if (r[0] <= b[0] && r[1] <= b[1])
hi = mid - 1;
else
lo = mid + 1;
}
return 0;
}
int ptr;
int key[2][99] = {
{1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 3, 3, 1, 3, 1, 1, 2, 3, 4, 2, 3, 4, 4, 1, 2, 3, 3, 4, 1, 5, 1, 2, 2, 3, 5, 3, 4, 5, 2, 5, 2, 3, 4, 5, 4, 4, 6, 1, 2, 3, 5, 6, 3, 4, 6, 5, 6, 1, 4, 5, 6, 1, 7, 1, 2, 2, 2, 3, 4, 5, 7, 3, 4, 7, 5, 6, 7, 2, 5, 6, 7, 2, 2, 3, 4, 5, 6, 8, 3, 4, 6, 8, 5, 8, 6, 8},
{2, 3, 4, 15, 17, 21, 26, 35, 52, 4, 5, 26, 35, 53, 5, 6, 35, 53, 7, 53, 8, 53, 9, 54, 10, 11, 12, 14, 16, 18, 22, 27, 36, 54, 2, 18, 22, 28, 37, 55, 2, 55, 2, 3, 8, 9, 10, 10, 11, 13, 14, 16, 19, 22, 28, 37, 56, 3, 28, 37, 56, 3, 4, 14, 16, 19, 23, 28, 38, 56, 4, 5, 23, 28, 38, 56, 5, 6, 28, 38, 57, 7, 38, 57, 8, 57, 9, 57, 10, 11, 12, 13, 15, 17, 19, 23, 29, 38, 57}
};
void solve(int N, int W, int l, int r, vector<int> candidates, int *P){
assert((int) candidates.size() == r - l + 1);
if (candidates.size() == 1){
P[candidates.front()] = l;
return;
}
vector<int> toLeft, toRight;
int k = key[W / N - 1][ptr++];
while (toLeft.empty() || toRight.empty()){
int b[N], r[N];
memset(b, 0, sizeof(b));
for(int x : candidates)
b[x] = k;
playRound(b, r);
toLeft.clear();
toRight.clear();
for(int x : candidates)
if (r[x] <= b[x])
toLeft.push_back(x);
else
toRight.push_back(x);
}
solve(N, W, l, l + toLeft.size() - 1, toLeft, P);
solve(N, W, l + toLeft.size(), r, toRight, P);
}
void allValues(int N, int W, int *P) {
ptr = 0;
vector<int> a;
for(int i = 0; i < N; i++)
a.push_back(i);
solve(N, W, 1, N, a, P);
}
