#include "koala.h"
#include <bits/stdc++.h>
#define sz(v) (int)v.size()
#define pb push_back
using namespace std;
int minValue(int N, int W) {
// TODO: Implement Subtask 1 solution here.
// You may leave this function unmodified if you are not attempting this
// subtask.
int n = N;
int a[n], b[n];
memset(a, 0, sizeof(a));
a[0] = 1;
playRound(a, b);
for(int i = 0; i < n; ++i) {
if(b[i] == 0) {
return i;
}
}
return 0;
}
int maxValue(int N, int W) {
// TODO: Implement Subtask 2 solution here.
// You may leave this function unmodified if you are not attempting this
// subtask.
int n = N, a[n], b[n];
vector<int> v;
for(int i = 0; i < n; ++i) {
v.pb(i);
}
while(sz(v) > 1) {
int t = W / sz(v);
bool used[n];
memset(used, 0, sizeof(used));
for(auto x : v) used[x] = 1;
for(int i = 0; i < n; ++i) {
if(!used[i]) {
a[i] = 0;
} else {
a[i] = t;
}
}
playRound(a, b);
vector<int> to;
for(int i = 0; i < n; ++i) {
if(b[i] > t) {
to.pb(i);
}
}
v = to;
}
return v[0];
}
bool cmp(int i, int j, int n, int W) {
int a[n], b[n];
int l = 1, r = min(9, W / 2), ans = -1;
while(l <= r) {
int mid = (l + r) >> 1;
memset(a, 0, sizeof(a));
a[i] = a[j] = mid;
playRound(a, b);
if(a[i] >= b[i] && a[j] >= b[j]) {
r = mid - 1;
continue;
}
bool c = (a[i] < b[i]), d = (a[j] < b[j]);
if(c && d) {
l = mid + 1;
continue;
}
ans = (c < d);
break;
}
assert(ans != -1);
return ans;
}
int greaterValue(int N, int W) {
// TODO: Implement Subtask 3 solution here.
// You may leave this function unmodified if you are not attempting this
// subtask.
return cmp(0, 1, N, W);
}
bool comp(int i, int j, int n) {
int a[n], b[n];
memset(a, 0, sizeof(a));
a[i] = a[j] = n;
playRound(a, b);
assert((b[i] > a[i]) || (b[j] > a[j]));
if(b[i] < a[i]) {
return 1;
}
return 0;
}
void calc(int l, int r, vector<int> &v, vector<int> &temp, int n, int w) {
if(l == r) {
return;
}
int mid = (l + r) >> 1;
calc(l, mid, v, temp, n, w);
calc(mid + 1, r, v, temp, n, w);
int timer = l, i = l, j = mid + 1;
while(i <= mid && j <= r) {
if((w == 2 * n ? comp(v[i], v[j], sz(v)) : cmp(v[i], v[j], n, w))) {
temp[timer++] = v[i++];
continue;
}
temp[timer++] = v[j++];
}
for(int k = i; k <= mid; ++k) temp[timer++] = v[k];
for(int k = j; k <= r; ++k) temp[timer++] = v[k];
for(int i = l; i <= r; ++i) v[i] = temp[i];
}
int timer;
vector<int> solve(vector<int> &v, int tl, int tr, int n, int W) {
if(sz(v) <= 1 || tl > tr) {
return v;
}
int c = min((int)sqrt(2 * tr), W / sz(v));
int a[n], b[n];
memset(a, 0, sizeof(a));
for(auto x : v) {
a[x] = c;
}
playRound(a, b);
vector<int> l, r;
for(auto x : v) {
if(a[x] < b[x]) {
r.pb(x);
} else {
l.pb(x);
}
}
if(l.empty() || r.empty()) {
vector<int> op = v;
calc(0, sz(v) - 1, v, op, n, W);
return v;
}
l = solve(l, tl, tl + sz(l) - 1, n, W);
r = solve(r, tl + sz(l), tr, n, W);
for(auto x : r) {
l.pb(x);
}
return l;
}
void allValues(int N, int W, int *P) {
if (W == 2*N) {
// TODO: Implement Subtask 4 solution here.
// You may leave this block unmodified if you are not attempting this
// subtask.
int n = N;
vector<int> v, p;
for(int i = 1; i <= n; ++i) {
v.pb(i - 1);
}
p = v;
calc(0, n - 1, v, p, N, W);
for(int i = 0; i < n; ++i) {
P[v[i]] = i + 1;
}
} else {
// TODO: Implement Subtask 5 solution here.
// You may leave this block unmodified if you are not attempting this
// subtask.
int n = N, a[n], b[n];
vector<int> v;
for(int t = 0; t < n; ++t) {
v.pb(t);
}
v = solve(v, 1, n, n, W);
for(int i = 0; i < n; ++i) {
P[v[i]] = i + 1;
}
}
}
