#include "koala.h"
#include<bits/stdc++.h>
#define vi vector<int>
#define pb push_back
using namespace std;
int minValue(int n, int W) { //N=W
int* A = new int[n];
int* B = new int[n];
for (int i=0;i<n;i++) A[i]=1;
playRound(A,B);
vi grandes;
for (int i=0;i<n;i++) if (B[i]==2) grandes.pb(i);
for (int i=0;i<n;i++) A[i]=0;
A[grandes[0]]=2;
A[grandes[1]]=n-2;
playRound(A,B);
for (int i=0;i<n;i++) if (i!=grandes[1] && B[i]==0) return i;
}
int maxValue(int n, int W) {
int* A = new int[n];
int* B = new int[n];
vi isgrande(n,1);
int grandes = n;
while (grandes>1){
int c=n%grandes;
for (int i=0;i<n;i++){
if (isgrande[i]) A[i]=n/grandes;
else if (c){
A[i]=1;
c--;
}
else A[i]=0;
}
playRound(A,B);
for (int i=0;i<n;i++) if (isgrande[i] && A[i]>=B[i]){
grandes--;
isgrande[i]=0;
}
}
for (int i=0;i<n;i++) if (isgrande[i]) return i;
assert(0);
}
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 0;
}
bool cmp(int a, int b){
if (a==b) return 0;
int* A = new int[100];
int* B = new int[100];
for (int i=0;i<100;i++) A[i]=0;
A[a]=A[b]=100;
// cerr << "q: ";
// for (int i=0;i<100;i++) cerr << A[i] << ' ';
playRound(A,B);
// cerr << endl;
// for (int i=0;i<100;i++) cerr << B[i] << ' ';
// cerr << endl;
return B[a]<=100;
}
void merge(std::vector<int>& vec, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
// Create temporary vectors
std::vector<int> leftVec(n1);
std::vector<int> rightVec(n2);
// Copy data to temporary vectors
for (int i = 0; i < n1; ++i)
leftVec[i] = vec[left + i];
for (int i = 0; i < n2; ++i)
rightVec[i] = vec[mid + 1 + i];
// Merge the temporary vectors back into vec[left..right]
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (cmp(leftVec[i], rightVec[j])) {
vec[k] = leftVec[i];
++i;
} else {
vec[k] = rightVec[j];
++j;
}
++k;
}
// Copy the remaining elements of leftVec, if any
while (i < n1) {
vec[k] = leftVec[i];
++i;
++k;
}
// Copy the remaining elements of rightVec, if any
while (j < n2) {
vec[k] = rightVec[j];
++j;
++k;
}
}
// Merge sort function
void mergeSort(std::vector<int>& vec, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
// Sort first and second halves
mergeSort(vec, left, mid);
mergeSort(vec, mid + 1, right);
// Merge the sorted halves
merge(vec, left, mid, right);
}
}
// Helper function to call mergeSort
void sortVector(std::vector<int>& vec) {
if (!vec.empty()) {
mergeSort(vec, 0, vec.size() - 1);
}
}
void allValues(int n, int W, int *P) {
if (W == 2*n) {
vi v(n);
for (int i=0;i<n;i++) v[i]=i;
sortVector(v);
for (int i=0;i<n;i++) P[v[i]]=i+1;
return;
} else {
// TODO: Implement Subtask 5 solution here.
// You may leave this block unmodified if you are not attempting this
// subtask.
}
}
