#include <bits/stdc++.h>
using namespace std;
#define all(a) (a).begin(), (a).end()
#define ll long long
#define ld long double
#define ui __int128_t
#define pb push_back
template<class T, class U> inline bool chmin(T& a, const U& b) { if (a > b) { a = b; return true; } return false; }
template<class T, class U> inline bool chmax(T& a, const U& b) { if (a < b) { a = b; return true; } return false; }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
static inline ll splix(ll x) {
x += 0x9e3779b97f4a7c15ULL;
ll z = x;
z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9ULL;
z = (z ^ (z >> 27)) * 0x94d049bb133111ebULL;
return z ^ (z >> 31);
}
/********* DEBUG *********/
__attribute__((constructor)) inline double ElapsedTime() {
using namespace std::chrono;
static const auto T0 = steady_clock::now();
return duration<double>(steady_clock::now() - T0).count();
}
template<typename T>
struct is_vector : false_type {};
template<typename T, typename A>
struct is_vector<vector<T, A>> : true_type {};
template<typename T>
void print_one(const T& x) {
if constexpr (is_vector<T>::value) {
for (size_t i = 0; i < x.size(); i++) {
cout << x[i];
if (i + 1 < x.size()) cout << ' ';
}
} else {
cout << x;
}
}
template<typename... Args>
void out(const Args&... args) {
bool first = true;
auto print_arg = [&](const auto& v) {
if (!first) cout << ' ';
first = false;
print_one(v);
};
(print_arg(args), ...);
// change to endl on interactives
cout << '\n';
}
/********* DEBUG *********/
#define fi first
#define se second
const ll MOD2 = 1e9 + 7;
const ll MOD = 998244353;
const ll inf = 1e18;
#include "koala.h"
int minValue(int N, int W) {
int put[N];
put[0] = 1;
for (int i = 1; i < N; i++)
put[i] = 0;
int koala[N];
playRound(put, koala);
if (0) for (auto &v : koala) {
out(v);
}
for (int i = 0; i < N; i++) {
if (put[i] >= koala[i]) {
return i;
}
}
// TODO: Implement Subtask 1 solution here.
// You may leave this function unmodified if you are not attempting this
// subtask.
return 0;
}
int maxValue(int N, int W) {
int B[N], R[N];
vector<ll> alive(N);
iota(all(alive), 0);
while (alive.size() > 1) {
for (int i = 0; i < N; i++) B[i] = 0;
ll val = W / alive.size();
for (auto &i : alive)
B[i] = val;
playRound(B, R);
alive.clear();
for (int i = 0; i < N; i++) {
if (R[i] > val)
alive.pb(i);
}
}
return alive[0];
}
int greaterValue(int N, int W) {
int B[N], R[N];
for (int i = 0; i < N; i++)
B[i] = 0;
ll l = 1, r = 9;
while (l <= r) {
ll m = (l + r) / 2;
B[0] = B[1] = m;
playRound(B, R);
if (R[0] > B[0] && R[1] > B[1]) {
l = m + 1;
} else if (R[0] <= B[0] && R[1] <= B[1]) {
r = m - 1;
} else {
return R[0] < R[1];
}
}
return -1;
}
void allValues(int N, int W, int *P) {
if (W == 2*N) {
auto lower = [&](ll l, ll r) -> bool {
int B[N], R[N];
for (int i = 0; i < N; i++) B[i] = 0;
B[l] = B[r] = 100;
playRound(B, R);
return R[l] <= 100;
};
auto merge = [&](auto &&merge, vector<ll> x) -> vector<ll> {
if (x.size() == 1) return x;
ll h = x.size() / 2;
vector<ll> l, r;
for (int i = 0; i < x.size(); i++) {
if (i < h) l.pb(x[i]);
else r.pb(x[i]);
}
l = merge(merge, l);
r = merge(merge, r);
vector<ll> ans;
ll i = 0, j = 0;
while (i < l.size() || j < r.size()) {
if (i == l.size()) {
ans.pb(r[j++]);
} else if (j == r.size()) {
ans.pb(l[i++]);
} else if (lower(r[j], l[i])) {
ans.pb(r[j++]);
} else {
ans.pb(l[i++]);
}
}
return ans;
};
vector<ll> x(N);
iota(all(x), 0);
vector<ll> sorted = merge(merge, x);
for (int i = 0; i < N; i++) {
P[sorted[i]] = i;
}
} else {
// TODO: Implement Subtask 5 solution here.
// You may leave this block unmodified if you are not attempting this
// subtask.
}
}
