#include <bits/stdc++.h>
#include "koala.h"
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 b[N], r[N];
memset(b, 0, sizeof(b)); b[0] = 1;
playRound(b, r);
if (r[0] <= 1) {
// he couldnt care less to take this
return 0;
}
// he could sad
for (int i = 1; i < N; i++) {
if (r[i] == 0) return i;
}
}
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.
vector<int> possible(N);
iota(begin(possible), end(possible), 0);
int b[N], r[N];
while (possible.size() > 1) {
int add = W / possible.size();
memset(b, 0, sizeof(b));
for (auto& i : possible) b[i] = add;
playRound(b, r);
possible.clear();
for (int i = 0; i < N; i++) if (r[i] > add) possible.push_back(i);
}
return possible[0];
}
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.
int b[N], R[N];
memset(b, 0, sizeof(b));
int l = 1, r = 13;
while (l <= r) {
int mid = (l + r) >> 1;
b[0] = mid, b[1] = mid;
playRound(b, R);
if (min(R[0], R[1]) > mid /*he took both so idk*/) l = mid + 1;
else if (max(R[0], R[1]) <= mid /*he took neither so spend less lol*/) r = mid - 1;
else {
if (R[0] < R[1]) return 1;
else return 0;
}
}
assert(false);
}
vector<int> ind;
int n, w;
bool compare(int i, int j) {
// is i < j?
int b[n], r[n];
memset(b, 0, sizeof(b));
b[i] = w / 2, b[j] = w / 2;
playRound(b, r);
return (r[j] * 2) > w;
}
vector<int> merge_sort(int l, int r) {
if (l == r) return vector<int>(1, l);
int mid = (l + r) >> 1;
auto left = merge_sort(l, mid), right = merge_sort(mid + 1, r);
vector<int> ret;
int i = 0, j = 0;
while (i < left.size() && j < right.size()) {
if (compare(left[i], right[j])) ret.push_back(left[i++]);
else ret.push_back(right[j++]);
}
while (i < left.size()) ret.push_back(left[i++]);
while (j < right.size()) ret.push_back(right[j++]);
return ret;
}
void allValues(int N, int W, int *P) {
n = N, w = W;
if (W == 2*N) {
// TODO: Implement Subtask 4 solution here.
// You may leave this block unmodified if you are not attempting this
// subtask.
ind.resize(N);
iota(begin(ind), end(ind), 0LL);
auto ans = merge_sort(0, N - 1);
for (int i = 0; i < N; i++) P[ans[i]] = i + 1;
} else {
// TODO: Implement Subtask 5 solution here.
// You may leave this block unmodified if you are not attempting this
// subtask.
}
}
