#include "koala.h"
#include <assert.h>
#include <vector>
int brue = 79, B[100], R[100], U[100], E[100];
void initialize(int N)
{
for(int i=0;i<N;i++)
{
B[i] = 0;
R[i] = 0;
}
return;
}
int minValue(int N, int W) {
initialize(N);
B[0] = 1;
playRound(B, R);
int ans = 0;
for(int i=1;i<N;i++)
{
if(R[i] == 0) ans = i;
}
return ans;
}
int maxValue(int N, int W) {
int cnt = N;
for(int i=0;i<N;i++) U[i] = true;
while(cnt > 1)
{
initialize(N);
for(int i=0;i<N;i++)
{
if(U[i]) B[i] = N/cnt;
}
playRound(B, R);
for(int i=0;i<N;i++)
{
if(R[i] <= B[i] && U[i])
{
U[i] = false;
cnt--;
}
}
}
for(int i=0;i<N;i++) if(U[i]) return i;
}
int greaterValue(int N, int W) {
int l = 1, r = 14;
while(l <= r)
{
initialize(N);
int mid = (2*l + r)/3;
B[0] = B[1] = mid;
playRound(B, R);
if(R[0] != R[1])
{
return (R[0] == 0) ? 1 : 0;
}
if(R[0] == 0) r = mid-1;
else l = mid+2;
}
}
int compare(int i, int j, int N)
{
initialize(N);
B[i] = B[j] = N;
playRound(B, R);
if(R[i] == 0) return j;
else return i;
}
void dnc(int l, int r, std::vector<int> v, int *P, int N)
{
if(l == r)
{
P[v[0]] = l;
return;
}
std::vector<int> small, big;
int siz = r - l + 1, val;
for(int k=1;k<=N/siz;k++)
{
int tmp = (k * siz) * (k*siz + 1) / 2;
tmp -= (k * (siz - 1)) * (k * (siz - 1) + 1) / 2;
if(tmp <= l) continue;
val = k; break;
}
initialize(N);
for(int i : v) B[i] = val;
playRound(B, R);
for(int i : v)
{
if(R[i] == 0) small.push_back(i);
else big.push_back(i);
}
assert(small.size() > 0 && big.size() > 0);
int a = small.size();
dnc(l, l+a-1,small,P,N);
dnc(l+a, r, big, P,N);
}
void allValues(int N, int W, int *P) {
if (W == 2*N) {
for(int i=0;i<N;i++) E[i] = 0;
for(int i=1;i<N;i++)
{
int l = 0, r = i;
while(l < r)
{
int mid = (l + r)/2;
if(compare(i, E[mid], N) == i) l = mid + 1;
else r = mid;
}
for(int j=N-1;j>l;j--) E[j] = E[j-1];
E[l] = i;
}
for(int i=0;i<N;i++)
{
P[E[i]] = i+1;
}
} else {
std::vector<int> v;
for(int i=0;i<N;i++) v.push_back(i);
dnc(1, N, v, P, N);
}
}
