#include "koala.h"
#include <bits/stdc++.h>
using namespace std;
int minValue(int N, int W) {
vector<int> B(N, 0), R(N, 0);
B[0] = 1;
playRound(B.data(), R.data());
if (R[0] < 2) return 0;
for (int i = 1; i < N; i++)
if (!R[i]) return i;
return 0;
}
int maxValue(int N, int W) {
vector<int> candidates, B(N, 0), R(N, 0);
for (int i = 0; i < N; i++) candidates.emplace_back(i);
while (candidates.size() > 1) {
int k = W / candidates.size();
fill(B.begin(), B.end(), 0);
for (int i : candidates) B[i] = k;
playRound(B.data(), R.data());
candidates.clear();
for (int i = 0; i < N; i++)
if (R[i] > k) candidates.emplace_back(i);
}
return candidates[0];
}
int greaterValue(int N, int W) {
int lo = 1, hi = 9;
vector<int> B(N, 0), R(N, 0);
while (lo != hi) {
int mid = (lo + hi) >> 1;
B[0] = B[1] = mid;
playRound(B.data(), R.data());
if (R[0] > mid && R[1] > mid) lo = mid+1;
else if (R[0] <= mid && R[1] <= mid) hi = mid-1;
else return (R[0] < R[1]);
}
B[0] = B[1] = lo;
playRound(B.data(), R.data());
return (R[0] < R[1]);
}
void allValues(int N, int W, int *P) {
if (W == 2*N) {
vector<int> B(N, 0), R(N, 0);
function<vector<int>(int, int)> merge_sort = [&](int lo, int hi) {
if (lo == hi) return vector<int>(1, lo);
int mid = (lo + hi) >> 1;
vector<int> Lef = merge_sort(lo, mid), Rig = merge_sort(mid+1, hi);
vector<int> ans;
int l = 0, r = 0;
while (l < Lef.size() || r < Rig.size()) {
if (l == Lef.size()) {ans.emplace_back(Rig[r]); ++r; continue;}
if (r == Rig.size()) {ans.emplace_back(Lef[l]); ++l; continue;}
int u = Lef[l], v = Rig[r];
B[u] = B[v] = W/2;
playRound(B.data(), R.data());
B[u] = B[v] = 0;
if (R[u] < R[v]) {
ans.emplace_back(Lef[l]); ++l;
} else {
ans.emplace_back(Rig[r]); ++r;
}
}
return ans;
};
vector<int> Lis = merge_sort(0, N-1);
for (int i = 0; i < N; i++) P[Lis[i]] = i+1;
} else {
vector<int> B(N, 0), R(N, 0);
function<void(vector<int>, int, int)> split = [&](vector<int> v, int lo, int hi) {
if (lo == hi) {
P[v[0]] = lo;
return;
}
int x = min(int(sqrt(2*lo)), W / (hi-lo+1));
fill(B.begin(), B.end(), 0);
for (int i : v) B[i] = x;
playRound(B.data(), R.data());
vector<int> lesser, morer;
for (int i : v)
if (R[i] > x) morer.emplace_back(i);
else lesser.emplace_back(i);
split(lesser, lo, lo+lesser.size()-1);
split(morer, lo+lesser.size(), hi);
};
vector<int> v(N, 0);
for (int i = 0; i < N; i++) v[i] = i;
split(v, 1, N);
}
}
