#include "koala.h"
#include <vector>
#include <set>
using namespace std;
int n, w;
int qb[100];
int qr[100];
int minValue(int N, int W) {
n = N;
w = W;
qb[0] = 1;
for (int i = 1; i < n; ++i) {
qb[i] = 0;
}
playRound(qb, qr);
for (int i = 0; i < n; ++i) {
if (qb[i] < qr[i]) continue;
return i;
}
}
int cand[100];
int maxValue(int N, int W) {
n = N;
w = W;
for (int i = 0; i < n; ++i) cand[i] = 1;
int cnt = n;
while (cnt > 1) {
for (int i = 0; i < n; ++i) {
if (cand[i]) qb[i] = w / cnt;
else qb[i] = 0;
}
playRound(qb, qr);
for (int i = 0; i < n; ++i) {
if (cand[i] && qr[i] <= qb[i]) --cnt, cand[i] = 0;
}
}
for (int i = 0; i < n; ++i) {
if (cand[i]) return i;
}
}
int greaterValue(int N, int W) {
n = N;
w = W;
for (int i = 0; i < n; ++i) {
qb[i] = 0;
}
const int arr[5] = { 1, 2, 3, 5, 8 };
int s = 0, e = 4;
while (s <= e) {
int m = (s + e) / 2;
qb[0] = qb[1] = arr[m];
playRound(qb, qr);
int a = (qb[0] < qr[0]);
int b = (qb[1] < qr[1]);
if (a != b) return b;
if (a) s = m + 1;
else e = m - 1;
}
}
int sortArray[100];
bool cmp(int x, int y) {
for (int i = 0; i < n; ++i) {
qb[i] = 0;
}
qb[x] = qb[y] = n;
playRound(qb, qr);
if (qb[x] < qr[x]) return 0;
return 1;
}
void mergeSort(int s, int e) {
if (e <= s) return;
int m = (s + e) / 2;
mergeSort(s, m);
mergeSort(m + 1, e);
int tp[100];
int i = s, j = m + 1, k = s;
while (i <= m || j <= e) {
if (i > m) tp[k++] = sortArray[j++];
else if (j > e) tp[k++] = sortArray[i++];
else if (cmp(sortArray[i], sortArray[j])) tp[k++] = sortArray[i++];
else tp[k++] = sortArray[j++];
}
for (i = s; i <= e; ++i) {
sortArray[i] = tp[i];
}
}
int saveFinds[101];
int findNineMax(const set<int> &mp) {
for (int i = 0; i < n; ++i) {
qb[i] = 0;
}
for (int i : mp) qb[i] = 11;
for (int i = mp.size(); i < 9; ++i) qb[saveFinds[i]] = 11;
playRound(qb, qr);
for (int i : mp) {
if (qb[i] < qr[i]) return i;
}
}
void findNumbers(int s, int e, int qs = 0) {
const int qn[3] = { 2, 4, 3 };
if (e - s < 9) {
set<int> mp;
for (int i = s; i <= e; ++i) mp.insert(saveFinds[i]);
for (int i = e; i > s; --i) {
mp.erase(saveFinds[i] = findNineMax(mp));
}
saveFinds[s] = *mp.begin();
return;
}
for (int i = 0; i < n; ++i) {
qb[i] = 0;
}
for (int i = s; i <= e; ++i) {
qb[saveFinds[i]] = qn[qs];
}
playRound(qb, qr);
vector<int> tp1, tp2;
for (int i = s; i <= e; ++i) {
if (qb[saveFinds[i]] < qr[saveFinds[i]]) tp2.push_back(saveFinds[i]);
else tp1.push_back(saveFinds[i]);
}
int i = s;
for (int j : tp1) saveFinds[i++] = j;
for (int j : tp2) saveFinds[i++] = j;
i = s + tp1.size();
findNumbers(s, i - 1, qs + 1);
findNumbers(i, e, qs + 1);
}
void allValues(int N, int W, int *P) {
n = N;
w = W;
if (W == N + N) {
for (int i = 0; i < n; ++i) {
sortArray[i] = i;
}
mergeSort(0, n - 1);
for (int i = 0; i < n; ++i) {
P[sortArray[i]] = i + 1;
}
} else {
int arr[100];
set<int> mp;
for (int i = 0; i < n; ++i) mp.insert(i);
for (int i = 0; i < n / 2; ++i) {
for (int j = 0; j < n; ++j) {
qb[j] = 0;
arr[j] = 1;
}
for (int j = 0; j < i; ++j) {
qb[saveFinds[j]] = 1;
arr[saveFinds[j]] = 0;
}
for (int j = 0, k = 0; j < n && k <= i; ++j) {
if (qb[j]) continue;
qb[j] = 1;
++k;
}
playRound(qb, qr);
for (int j = 0; j < n; ++j) {
if (arr[j] && qr[j] <= qb[j]) {
saveFinds[i] = j;
mp.erase(j);
break;
}
}
}
for (int i = n / 2; i < n; ++i) {
saveFinds[i] = *mp.begin();
mp.erase(mp.begin());
}
findNumbers(n / 2, n - 1);
for (int i = 0; i < n; ++i) {
P[saveFinds[i]] = i + 1;
}
}
}
