#include "koala.h"
#include <bits/stdc++.h>
using namespace std;
// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e9
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
#define sz size()
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MX=500;
int B[MX], R[MX];
int minValue(int N, int W) {
RE(i,N) B[i] = 0;
B[1] = 1;
playRound(B,R);
RE(i,N) if(R[i] == 0) return i;
return 0;
}
int maxValue(int N, int W) {
vi possible;
RE(i,N) possible.push_back(i);
while(possible.size() > 1) {
int weight = W / possible.size();
RE(i,N) B[i] = 0;
FOR(u,possible) B[u] = weight;
playRound(B,R);
possible.clear();
RE(i,N) if(R[i] > weight) possible.push_back(i);
}
return possible[0];
}
int greaterValue(int N, int W, int i, int j) {
int lb=1, ub=10;
while(lb != ub) {
int mid=(lb+ub)/2;
RE(i,N) B[i] = 0;
B[i] = mid;
B[j] = mid;
playRound(B,R);
if(R[i] <= mid && R[j] <= mid) ub=mid-1;
if(R[i] > mid && R[j] > mid) lb=mid+1;
if(R[i] <= mid && R[j] > mid) return j;
if(R[i] > mid && R[j] <= mid) return i;
}
RE(i,N) B[i] = 0;
B[i] = lb;
B[j] = lb;
playRound(B,R);
if(R[i] <= lb && R[j] > lb) return j;
if(R[i] > lb && R[j] <= lb) return i;
return i;
}
int greaterValue(int N, int W) {
return greaterValue(N,W,0,1);
}
void findValues1(int N, int W, int lb, int ub, vi f, int *P) {
if(f.size() == 1) {
P[f[0]] = lb;
return;
}
int weight = W / f.size();
RE(i,N) B[i] = 0;
FOR(u,f) B[u] = weight;
playRound(B,R);
vi left;
vi right;
FOR(u,f) (R[u] > weight ? right : left).push_back(u);
findValues1(N,W,lb,lb+left.size()-1,left,P);
findValues1(N,W,ub-right.size()+1,ub,right,P);
}
void findValues2(int N, int W, int lb, int ub, vi f, int *P) {
if(f.size() == 1) {
P[f[0]] = lb;
return;
}
int LB=1, UB=(W + N - ub)/f.size();
while(true) {
int mid=(LB+UB)/2;
RE(i,N) B[i] = 0;
FOR(u,f) B[u] = mid;
playRound(B,R);
vi left;
vi right;
FOR(u,f) (R[u] > mid ? right : left).push_back(u);
if(left.empty()) LB=mid+1;
else if(right.empty()) UB=mid-1;
else {
findValues2(N,W,lb,lb+left.size()-1,left,P);
findValues2(N,W,ub-right.size()+1,ub,right,P);
break;
}
}
}
void allValues(int N, int W, int *P) {
vi f;
RE(i,N) f.push_back(i);
if (W == 2*N) {
findValues1(N,W,1,N,f,P);
} else {
findValues2(N,W,1,N,f,P);
}
}
