#include "koala.h"
#include <vector>
#include <set>
#include <iostream>
#include <map>
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=new int[n];
int* r=new int[n];
b[0]=1;
playRound(b,r);
for(int i=0;i<n;i++)
{
if(r[i]==0)
return i;
}
return 0;
}
int maxValue(int n, int w) {
int* b=new int[n];
int* r=new int[n];
for(int i=0;i<n;i++)b[i]=1;
playRound(b,r);
set<int> pos;
for(int i=0;i<n;i++)
{
if(r[i]>0)
{
pos.insert(i);
// cout<<i<<' ';
}
}
// cout<<endl;
for(int i=0;i<n;i++)
{
b[i]=0;
}
for(auto x:pos)
{
b[x]=2;
}
playRound(b,r);
pos.clear();
for(int i=0;i<n;i++)
{
if(r[i]>0 and b[i]==2)
{
pos.insert(i);
// cout<<i<<' ';
}
}
// cout<<endl;
for(int i=0;i<n;i++)
{
b[i]=0;
}
for(auto x:pos)
{
b[x]=4;
}
playRound(b,r);
pos.clear();
for(int i=0;i<n;i++)
{
if(r[i]>0 and b[i]==4)
{
pos.insert(i);
// cout<<i<<' ';
}
}
// cout<<endl;
for(int i=0;i<n;i++)
{
b[i]=0;
}
for(auto x:pos)
{
b[x]=11;
}
playRound(b,r);
pos.clear();
for(int i=0;i<n;i++)
{
if(r[i]>0 and b[i]==11)
{
return i;
// pos.insert(i);
// cout<<i<<' ';
}
}
// cout<<endl;
return 0;
}
const int MPL=500;
int fnl[MPL],n,w;
int* b;
int* rt;
void Simulate(int *B, int *R) {
int i, j;
int S = 0;
for (i=0;i<n;++i) {
S += B[i];
}
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 recur(int l,int r,set<int>&ind)
{
if(l==r)
{
fnl[*begin(ind)]=l;
return;
}
for(int i=0;i<n;i++)b[i]=0;
int bst=1,dif=ind.size();
for(int pl=1;pl<=(w/(int)ind.size());pl++)
{
for(int x=l;x<=r;x++)
{
b[x-1]=pl;
}
Simulate(b,rt);
set<int> high,low;
for(int x=l-1;x<=r-1;x++)
{
if(rt[x]>b[x])
{
high.insert(x);
}
else
{
low.insert(x);
}
}
int cdif=abs((int)low.size() - (int)high.size());
if(cdif<dif)
{
dif=cdif;
bst=pl;
}
}
for(int i=0;i<n;i++)b[i]=0;
for(auto x:ind)
{
b[x]=bst;
}
playRound(b,rt);
set<int> high,low;
for(auto x:ind)
{
if(rt[x]>b[x])
{
high.insert(x);
}
else
{
low.insert(x);
}
}
if(low.size()==0 or high.size()==0)return;
recur(l,r-(int)high.size(),low);
recur(l+(int)low.size(),r,high);
}
void allValues(int N, int W, int *P) {
::n=N;
::w=W;
b=new int[n];
rt=new int[n];
set<int> cur;
for(int i=0;i<n;i++)cur.insert(i);
recur(1,n,cur);
for(int i=0;i<n;i++)
{
P[i]=fnl[i];
}
}
int recur_spe(int l,int r,set<int>&ind)
{
if(l==r)
{
fnl[*begin(ind)]=l;
return -1;
}
for(int i=0;i<n;i++)b[i]=0;
int bst=1,dif=-1,len=(r-l+1);
for(int pl=1;pl<=(w/(int)ind.size());pl++)
{
for(int x=l;x<=r;x++)
{
b[x-1]=pl;
}
Simulate(b,rt);
set<int> high,low;
for(int x=l-1;x<=r-1;x++)
{
if(rt[x]>b[x])
{
high.insert(x);
}
else
{
low.insert(x);
}
}
int cdif=abs((int)low.size() - (int)high.size());
if(low.size()>0 and high.size()>0 and cdif<=(len/3) and cdif>=dif)
{
dif=cdif;
bst=pl;
}
}
for(int i=0;i<n;i++)b[i]=0;
for(auto x:ind)
{
b[x]=bst;
}
playRound(b,rt);
set<int> high,low;
for(auto x:ind)
{
if(rt[x]>b[x])
{
high.insert(x);
}
else
{
low.insert(x);
}
}
if((low.find(0)!=low.end() and low.find(1)!=low.end()))
{
// both in the same bucket
return recur_spe(l,r-(int)high.size(),low);
}
else if((high.find(0)!=high.end() and high.find(1)!=high.end()))
{
return recur_spe(l+(int)low.size(),r,high);
}
else
{
// both in different buckets
return (high.find(0)==high.end());
}
}
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.
::n=n;
::w=w;
b=new int[n];
rt=new int[n];
set<int> cur;
for(int i=0;i<n;i++)cur.insert(i);
return recur_spe(1,n,cur);
// return ;
}
