#include "koala.h"
#include <bits/stdc++.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];
for (int i=0;i<N;i++){
b[i] = 0;
}
b[0] = 1;
playRound(b,r);
for (int i=0;i<100;i++){
if (r[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 b[N],r[N];
for (int i=0;i<N;i++){
b[i] = 1;
}
//b[0] = 1;
playRound(b,r);
queue<int> next;
for (int i=0;i<N;i++){
if (r[i]==2) next.push(i);
}
for (int i=0;i<N;i++){
b[i] = 0;
}
while (!next.empty()) {
b[next.front()]=2;
next.pop();
}
playRound(b,r);
for (int i=0;i<N;i++){
if (r[i]==3) next.push(i);
}
for (int i=0;i<N;i++){
b[i] = 0;
}
while (!next.empty()) {
b[next.front()]=4;
next.pop();
}
playRound(b,r);
for (int i=0;i<N;i++){
if (r[i]==5) next.push(i);
}
for (int i=0;i<N;i++){
b[i] = 0;
}
while (!next.empty()) {
b[next.front()]=11;
next.pop();
}
playRound(b,r);
for (int i=0;i<N;i++){
if (r[i]==12) return i;
}
return 0;
}
int compare(int a, int bb){
int N=100;
int b[N],r[N];
for (int i=0;i<N;i++){
b[i] = 1;
}
//b[0] = 1;
playRound(b,r);
queue<int> next;
int grp[100];
vector<int> grps[5];
for (int i=0;i<N;i++){
if (r[i]==2) next.push(i);
if (r[i]==2){
grp[i]=3;
}
else grp[i]=1;
}
for (int i=0;i<N;i++){
b[i] = 0;
}
while (!next.empty()) {
b[next.front()]=2;
next.pop();
}
playRound(b,r);
for (int i=0;i<N;i++){
if (r[i]==3) next.push(i);
if (r[i]==3) grp[i] = 4;
else if (r[i]==1) grp[i] = 2;
}
for (int i=0;i<N;i++){
grps[grp[i]].push_back(i);
}
if (grp[a]>grp[bb]) return a;
else if (grp[a]<grp[bb]) return bb;
for (int i=0;i<N;i++){
b[i] = 0;
}
if (grp[a]==2){
b[a]=6;
b[bb]=6;
}
else if (grp[a]==3){
b[a]=8;
b[bb]=8;
}
else if (grp[a]==4){
b[a]=10;
b[bb]=10;
}
else{
for (int i=0;i<N;i++){
b[i] = 1;
}
b[a]=0;
b[bb]=0;
b[grps[4][0]]=0;
}
playRound(b,r);
if (r[a]!=0) return a;
else return bb;
}
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 compare(0,1);
}
void all1(int *P){
int b[100],r[100],a[100];
for (int i=0;i<100;i++) a[i] = i;
stable_sort(a,a+100,[&](int aa,int bb){
memset(b,0,sizeof(b));
b[aa]=100;
b[bb]=100;
playRound(b,r);
if (r[aa]==0) return true;
return false;
});
for (int i=0;i<100;i++){
P[a[i]]=i+1;
}
}
void playRound2(int *B, int *R) {
int i, j;
int S = 0;
int N=100,W=100;
for (i=0;i<N;++i) {
if ( !(B[i] >= 0 && B[i] <= W) ) {
//cout << B[i];
printf("Invalid query.\n");
exit(0);
}
S += B[i];
}
if (S > W) {
printf("Invalid query.\n");
exit(0);
}
int cache[2][205];
int num[2][205];
char taken[105][205];
for (i=0;i<205;++i) {
cache[1][i] = 0;
num[1][i] = 0;
}
for (i=0;i<N;++i) {
int v = B[i]+1;
int ii = i&1;
int o = ii^1;
for (j=0;j<=W;++j) {
cache[ii][j] = cache[o][j];
num[ii][j] = num[o][j];
taken[i][j] = 0;
}
for (j=W;j>=v;--j) {
int h = cache[o][j-v] + i+1;
int hn = num[o][j-v] + 1;
if (h > cache[ii][j] || (h == cache[ii][j] && hn > num[ii][j])) {
cache[ii][j] = h;
num[ii][j] = hn;
taken[i][j] = 1;
} else {
taken[i][j] = 0;
}
}
}
int cur = W;
for (i=N-1;i>=0;--i) {
R[i] = taken[i][cur] ? (B[i] + 1) : 0;
cur -= R[i];
}
}
void all2(int *P, int s, int e, vector<int> next){
if (next.size()==1) {
P[next[0]]=s;
return;
}
int b[100],r[100],b2[100],r2[100];
memset(b,0,sizeof(b));
memset(b2,0,sizeof(b2));
for (int i=1;i<=100;i++){
for (int j=s-1;j<e;j++) b2[j]=i;
playRound2(b2,r2);
int pass=0;
for (int j=s-1;j<e;j++){
if (r2[j]==0) pass=1;
}
if (pass==0) continue;
for (auto item:next){
b[item]=i;
}
playRound(b,r);
vector<int> left,right;
for (auto item:next){
if (r[item]==0) left.push_back(item);
else right.push_back(item);
}
// cout << "left: ";
// for (auto item:left) cout << item << " ";
// cout << "\nright: ";
// for (auto item:right) cout << item << " ";
// cout << "\n";
if (left.empty()||right.empty()) continue;
all2(P,s,left.size()+s-1,left);
all2(P,left.size()+s,e,right);
return;
}
}
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.
all1(P);
} else {
// TODO: Implement Subtask 5 solution here.
// You may leave this block unmodified if you are not attempting this
// subtask.
vector<int> next;
for (int i=0;i<100;i++) next.push_back(i);
all2(P,1,N,next);
}
}
