#include "koala.h"
#include <algorithm>
#include <bits/stdc++.h>
#include <ostream>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX_N = 100;
int B[MAX_N], R[MAX_N];
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.
memset(B, 0, sizeof B);
B[0] = 1;
playRound(B, R);
int zero_pos = find(R, R+N, 0) - R;
return zero_pos;
}
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.
for (int i=0; i<N; ++i) B[i] = 1;
playRound(B, R);
vector<int> half_large;
for (int i=0; i<N; ++i) {
if (R[i] == 2) half_large.push_back(i);
}
assert(half_large.size() == 50);
memset(B, 0, sizeof B);
for (int i: half_large) B[i] = 2;
playRound(B, R);
vector<int> quarter_large;
for (int i=0; i<N; ++i) {
if (R[i] == 3) quarter_large.push_back(i);
}
memset(B, 0, sizeof B);
for (int i: quarter_large) B[i] = 4;
playRound(B, R);
vector<int> ninetyone_large;
for (int i=0; i<N; ++i) {
if (R[i] > 1) ninetyone_large.push_back(i);
}
memset(B, 0, sizeof B);
for (int i: ninetyone_large) B[i] = 11;
playRound(B, R);
return find(R, R+N, 12) - R;
}
void sub3_helper(int x) {
memset(B, 0, sizeof B);
B[0] = B[1] = x;
playRound(B, R);
}
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.
sub3_helper(4);
if (R[0] == R[1]) {
if (R[0] == 0) {
sub3_helper(2);
if (R[0] != R[1]) {
// cout << "2 ";
return R[0] < R[1];
}
sub3_helper(1);
// cout << "1 ";
return R[0] < R[1];
} else {
sub3_helper(8);
// cout << "8 ";
return R[0] < R[1];
}
} else {
// cout << "4 ";
return R[0] < R[1];
}
}
void sub4_helper(int i, int j) {
B[i] = B[j] = 100;
playRound(B, R);
B[i] = B[j] = 0;
}
void sub5_helper(int N, vector<int>& arr, int thres) {
// cout << thres << ' ';
// for (int x: arr) cout << x << ' ';
// cout << endl;
if (arr.size() == 1) return;
if (arr.size() == 0) assert(false);
memset(B, 0, sizeof B);
for (int x: arr) B[x] = thres;
playRound(B, R);
vector<int> big, small;
for (int i=0; i<N; ++i) {
if (R[i] >= thres+1) big.push_back(i);
}
for (int x: arr) {
if (find(big.begin(), big.end(), x) == big.end()) small.push_back(x);
}
if (small.size() == 0) {
sub5_helper(N, big, thres+1);
} else {
sub5_helper(N, small, thres);
sub5_helper(N, big, thres);
}
arr.clear();
for (int x: small) arr.push_back(x);
for (int x: big) arr.push_back(x);
}
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.
vector<int> ord = { 0 };
for (int i=1; i<N; ++i) {
int l = 0, r = i; // bar model
while (l < r) {
int mid = (l+r) / 2;
sub4_helper(ord[mid], i);
if (R[ord[mid]] < R[i]) {
l = mid+1;
} else {
r = mid;
}
}
vector<int> tmp;
for (int i=0; i<l; ++i) tmp.push_back(ord[i]);
tmp.push_back(i);
for (int i=l; i<ord.size(); ++i) tmp.push_back(ord[i]);
ord = tmp;
}
for (int i=0; i<N; ++i) P[ord[i]] = i+1;
} else {
// TODO: Implement Subtask 5 solution here.
// You may leave this block unmodified if you are not attempting this
// subtask.
int min_pos = minValue(N, W);
vector<vector<int>> q(8);
// [1, 100] -> [1], [2, 50], [51, 100]
fill(B, B+N, 1);
playRound(B, R);
for (int i=0; i<N; ++i) {
if (R[i] >= 2) q[4].push_back(i);
else q[0].push_back(i);
}
q[0].erase(find(q[0].begin(), q[0].end(), min_pos));
// [1, 50] -> [1, 25], [26, 50]
memset(B, 0, sizeof B);
for (int x: q[0]) B[x] = 1;
playRound(B, R);
for (int i=0; i<N; ++i) {
if (R[i] >= 2) {
q[2].push_back(i);
auto it = find(q[0].begin(), q[0].end(), i);
q[0].erase(it);
}
}
// [2, 25] -> [2, 13], [14, 25]
memset(B, 0, sizeof B);
for (int x: q[0]) B[x] = 1;
playRound(B, R);
for (int i=0; i<N; ++i) {
if (R[i] >= 2) {
q[1].push_back(i);
auto it = find(q[0].begin(), q[0].end(), i);
q[0].erase(it);
}
}
// [2, 13] -> [2, 7], [8, 13]
vector<int> lq0, rq0;
memset(B, 0, sizeof B);
for (int x: q[0]) B[x] = 1;
playRound(B, R);
for (int i=0; i<N; ++i) {
if (R[i] >= 2) rq0.push_back(i);
}
for (int x: q[0]) {
if (find(rq0.begin(), rq0.end(), x) == rq0.end()) lq0.push_back(x);
}
// [26, 50] -> [26, 38], [39, 50]
memset(B, 0, sizeof B);
for (int x: q[1]) B[x] = 2;
for (int x: q[2]) B[x] = 3;
playRound(B, R);
for (int i=0; i<N; ++i) {
if (R[i] >= 4) {
q[3].push_back(i);
auto it = find(q[2].begin(), q[2].end(), i);
q[2].erase(it);
}
}
// [51, 100] -> [51, 75], [76, 100]
memset(B, 0, sizeof B);
for (int x: q[4]) B[x] = 2;
playRound(B, R);
for (int i=0; i<N; ++i) {
if (R[i] >= 3) {
q[6].push_back(i);
auto it = find(q[4].begin(), q[4].end(), i);
q[4].erase(it);
}
}
// [51, 75] -> [51, 63], [64, 75]
memset(B, 0, sizeof B);
for (int x: q[0]) B[x] = 1;
for (int x: q[1]) B[x] = 1;
for (int x: q[4]) B[x] = 3;
playRound(B, R);
for (int i=0; i<N; ++i) {
if (R[i] >= 4) {
q[5].push_back(i);
auto it = find(q[4].begin(), q[4].end(), i);
q[4].erase(it);
}
}
// [76, 100] -> [76, 88], [89, 100]
memset(B, 0, sizeof B);
for (int x: q[6]) B[x] = 3;
playRound(B, R);
for (int i=0; i<N; ++i) {
if (R[i] >= 4) {
q[7].push_back(i);
auto it = find(q[6].begin(), q[6].end(), i);
q[6].erase(it);
}
}
sub5_helper(N, lq0, 2);
sub5_helper(N, rq0, 3);
sub5_helper(N, q[1], 4);
for (int i=2; i<7; ++i) sub5_helper(N, q[i], 7);
sub5_helper(N, q[7], 8);
// for (int i=6; i<8; ++i) sub5_helper(N, q[i], 8);
P[min_pos] = 1;
for (int i=2; i<=7; ++i) P[lq0[i-2]] = i;
for (int i=8; i<=13; ++i) P[rq0[i-8]] = i;
for (int i=14; i<=25; ++i) P[q[1][i-14]] = i;
for (int i=26; i<=38; ++i) P[q[2][i-26]] = i;
for (int i=39; i<=50; ++i) P[q[3][i-39]] = i;
for (int i=51; i<=63; ++i) P[q[4][i-51]] = i;
for (int i=64; i<=75; ++i) P[q[5][i-64]] = i;
for (int i=76; i<=88; ++i) P[q[6][i-76]] = i;
for (int i=89; i<=100; ++i) P[q[7][i-89]] = i;
// memset(B, 0, sizeof B);
// for (int i=13; i<25; ++i) B[i] = 2;
// for (int i=25; i<50; ++i) B[i] = 3;
// playRound(B, R);
// for (int i=0; i<N; ++i) cout << R[i] << ' ';
// cout << endl;
// cout << find(R, R+N, 4) - R << endl;
}
}
