#include "koala.h"
#include<bits/stdc++.h>
using namespace std;
int sub = 0;
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];
B[0] = 1;
for(int i = 1 ; i < N ;i++)
{
B[i] = 0;
R[i] = 0;
}
playRound(B , R);
for(int i = 0 ;i < N ; i++)
{
if(R[i] <= B[i])
{
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];
// cout<<"HELLO\n";
for(int i = 0 ; i < N ;i++)
{
B[i] = 1;
R[i] = 0;
}
int nb1 = N;
int ret = 0;
vector<bool> bad(N);
while(nb1 > 1)
{
// cout<<"B : ";
// for(int i = 0 ; i < N ; i++)
// {
// cout<<B[i]<<" ";
// }
// cout<<'\n';
playRound(B , R);
// cout<<"R : ";
// for(int i = 0 ; i < N ; i++)
// {
// cout<<R[i]<< " ";
// }
// cout<<'\n';
nb1 = 0;
for(int i = 0 ; i < N ; i++)
{
if(bad[i])
continue;
if(R[i] <= B[i])
{
bad[i] = 1;
B[i] = 0;
}
else
{
B[i]++;
nb1++;
ret = i;
}
}
}
return ret;
}
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.
int lo = 0 , hi = 10;
int a = 0 , b = 1;
while(lo + 1 < hi)
{
int md = (lo + hi) / 2ll;
int B[N] , R[N];
for(int i = 0 ; i < N ; i++)
{
B[i] = 0;
R[i] = 0;
}
B[a] = md;
B[b] = md;
playRound(B , R);
int aa = (R[a] > B[a]);
int bb = (R[b] > B[b]);
if(aa == 0 && bb == 0)
{
hi = md;
}
else if(aa == 1 && bb == 1)
{
lo = md;
}
else
return bb;
}
return 1;
}
bool cmp(const int &a, const int &b ) {
int N = 100;
if(a == b)
return 0;
if(sub == 0)
{
int B[N] , R[N];
for(int i = 0 ; i < N ; i++)
{
B[i] = 0 , R[i] = 0;
}
B[a] = N;
B[b] = N;
playRound(B , R);
if(R[b] > B[b])
return 1;
return 0;
}
else
{
int lo = 0 , hi = 10;
while(lo + 1 < hi)
{
int md = (lo + hi) / 2ll;
int B[N] , R[N];
for(int i = 0 ; i < N ; i++)
{
B[i] = 0;
R[i] = 0;
}
B[a] = md;
B[b] = md;
playRound(B , R);
int aa = (R[a] > B[a]);
int bb = (R[b] > B[b]);
if(aa == 0 && bb == 0)
{
hi = md - 1;
}
else if(aa == 1 && bb == 1)
{
lo = md + 1;
}
else
return bb;
}
return 1;
}
}
void merge(vector<int> &arr, int l, int mid, int r) {
int n1 = mid - l + 1;
int n2 = r - mid;
vector<int> L(n1), R(n2);
for (int i = 0; i < n1; i++) L[i] = arr[l + i];
for (int i = 0; i < n2; i++) R[i] = arr[mid + 1 + i];
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (cmp(L[i], R[j]))
arr[k++] = L[i++];
else
arr[k++] = R[j++];
}
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
void Sort(vector<int> &arr, int l, int r) {
if (l >= r) return;
int mid = l + (r - l) / 2;
Sort(arr, l, mid);
Sort(arr, mid + 1, r);
merge(arr, l, mid, r);
}
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> order(N);
iota(order.begin() , order.end() , 0);
Sort(order , 0 , N - 1);
for(int i = 0 ; i < N ; i++)
{
P[order[i]] = i + 1;
}
} else {
// TODO: Implement Subtask 5 solution here.
// You may leave this block unmodified if you are not attempting this
// subtask.
sub = 1;
vector<int> order(N);
iota(order.begin() , order.end() , 0);
Sort(order , 0 , N - 1);
for(int i = 0 ; i < N ; i++)
{
P[order[i]] = i + 1;
}
}
}
