#include "koala.h"
#include <bits/stdc++.h>
using namespace std;
int minValue(int n, int w)
{
int b[n];
int r[n];
for(int i = 1; i < n; i++)
{
b[i] = 0;
}
b[0] = 1;
playRound(b, r);
if(r[0] <= 1)
return 0;
for(int i = 1; i < n; i++)
{
if(r[i] == 0)
return i;
}
return 0;
}
int maxValue(int n, int w)
{
int b[n];
int r[n];
vector < int > maxset;
for(int i = 0; i < n; i++)
{
maxset.push_back(i);
}
while(maxset.size() > 1)
{
int sz = maxset.size();
int by = w / sz;
for(int i = 0; i < n; i++)
{
b[i] = 0;
}
for(int idx : maxset)
{
b[idx] = by;
}
playRound(b, r);
maxset.clear();
for(int i = 0; i < n; i++)
{
if(r[i] > by)
maxset.push_back(i);
}
}
return maxset[0];
return 0;
}
int n;
int w;
bool cmp(int idx1, int idx2, int *b, int *r)
{
int left = 0;
int right = 15;
int mid;
for(int i = 0; i < n; i++)
{
b[i] = 0;
}
while(right - left > 1)
{
mid = left + (right - left) / 2;
b[idx1] = b[idx2] = mid;
playRound(b, r);
b[idx1] = b[idx2] = 0;
if(r[idx1] <= mid && r[idx2] <= mid)
right = mid;
else if(r[idx1] > mid && r[idx2] > mid)
left = mid;
else
{
b[idx1] = b[idx2] = 0;
return r[idx1] < r[idx2];
}
}
b[idx1] = b[idx2] = left;
playRound(b, r);
b[idx1] = b[idx2] = 0;
return r[idx1] < r[idx2];
}
int greaterValue(int N, int W)
{
n = N;
w = W;
int b[n];
int r[n];
for(int i = 0; i < n; i++)
{
b[i] = 0;
}
return cmp(0, 1, b, r);
}
vector < int > a;
vector < int > tmp;
void merge_sort(int left, int right, int *b, int *r, int by)
{
if(left == right)
return;
int mid = left + (right - left) / 2;
merge_sort(left, mid, b, r, by);
merge_sort(mid + 1, right, b, r, by);
int ptrl = left;
int ptrr = mid + 1;
int ptr = left;
while(ptrl <= mid && ptrr <= right)
{
for(int i = 0; i < n; i++)
{
b[i] = 0;
}
b[a[ptrl]] = b[a[ptrr]] = by;
playRound(b, r);
if(r[a[ptrr]] > by)
{
tmp[ptr++] = a[ptrl++];
}
else
{
tmp[ptr++] = a[ptrr++];
}
}
while(ptrl <= mid)
tmp[ptr++] = a[ptrl++];
while(ptrr <= right)
tmp[ptr++] = a[ptrr++];
for(int i = left; i <= right; i++)
{
a[i] = tmp[i];
}
}
void fake_sort(vector < int > idxs, int left, int right, int *b, int *r, int *p)
{
//cout << "Left - Right : " << left << " - " << right << endl;
if(left > right)
return;
if(left == right)
{
p[idxs[0]] = left;
return;
}
int by = w / (right - left + 1);
for(int i = 0; i < n; i++)
{
b[i] = 0;
}
for(int idx : idxs)
{
b[idx] = by;
}
playRound(b, r);
vector < int > big, small;
for(int idx : idxs)
{
if(r[idx] > by)
big.push_back(idx);
else
small.push_back(idx);
}
fake_sort(big, right - big.size() + 1, right, b, r, p);
fake_sort(small, left, left + small.size() - 1, b, r, p);
}
void allValues(int N, int W, int *p)
{
n = N;
w = W;
int b[n];
int r[n];
if(w == n)
{
vector < int > idxs;
for(int i = 0; i < n; i++)
idxs.push_back(i);
fake_sort(idxs, 1, n, b, r, p);
}
else
{
for(int i = 0; i < n; i++)
{
b[i] = 0;
}
a.resize(n);
tmp.resize(n);
for(int i = 0; i < n; i++)
{
a[i] = i;
}
merge_sort(0, n - 1, b, r, w == 2 * n ? n : n / 2);
for(int i = 0; i < n; i++)
{
p[a[i]] = i + 1;
}
}
}
