#include "koala.h"
#include<bits/stdc++.h>
using namespace std;

int B[105], R[105];

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.
    return 0;
}
vector<int> search_set = {1, 2, 3, 5, 8};

int maxValue(int N, int W) {
    vector<int> vec = {1, 2, 4, 11};
    vector<int> good(N);
    iota(good.begin(), good.end(), 0);
    for(auto v: vec){
        fill(B, B + N, 0);
        for(auto id: good)B[id] = v;
        playRound(B, R);
        good.clear();
        for(int i = 0; i < N; i++)if(R[i] > v)good.push_back(i);
    }
    return good.back();
}

int greaterValue(int N, int W) {
    int l = 0, r = search_set.size()-1;
    while(l <= r){
        int md = (l+r)>>1;
        int mid = search_set[md];
        B[0] = B[1] = mid;
        playRound(B, R);
        if (R[0] > mid and R[1] <= mid) return 0;
        if (R[1] > mid and R[0] <= mid) return 1;
        if(R[0] > mid && R[1] > mid)l = md + 1;
        else r = md - 1;
    }
    return 0;

    // k p0 <= sum (k+1)so dau tien < p1
}

int n;

// 1-3, 3-9, 6-18, 15-45, 36-100
int bound[9][2] = {
    {0, 0},
    {0, 4},
    {2, 10},
    {5, 19},
    {9, 31},
    {14, 46},
    {20, 64},
    {27, 85},
    {35, 101}
};

int cbound[105][2];

int cnt[105][2];
bool recmp[105][105];
int ans[105];

bool cmp(int a, int b){
    assert(a != b);
    if(recmp[a][b])return 1;
    if(recmp[b][a])return 0;
    int la = max(cnt[a][0] - 1, cbound[a][0]), ra = min(100 - cnt[a][1], cbound[a][1]);
    int lb = max(cnt[b][0] - 1, cbound[b][0]), rb = min(100 - cnt[b][1], cbound[b][1]);
    if(la >= rb){
        cnt[a][0]++;
        cnt[b][1]++;
        recmp[b][a] = 1;
        return 0;
    }
    if(lb >= ra){
        recmp[a][b] = 1;
        cnt[b][0]++;
        cnt[a][1]++;
        return 1;
    }
    int l = -1, r = -1;
    for(int i = 0; i < search_set.size(); i++){
        if(bound[search_set[i]][0] >= min(ra, rb) || bound[search_set[i]][1] <= max(la, lb))continue;
        if(l == -1)l = i;
        r = i;
    }
    while(l <= r){
        int md = (l+r)>>1;
        int mid = search_set[md];
        fill(B, B+n, 0);
        B[a] = B[b] = mid;
        playRound(B, R);
        // cout << mid << " " << R[a] << " " << R[b] << endl;
        if (R[a] > mid and R[b] <= mid) {
            cnt[a][0]++;
            cnt[b][1]++;
            recmp[b][a] = 1;
            return 0;
        }
        if (R[b] > mid and R[a] <= mid) {
            cnt[b][0]++;
            cnt[a][1]++;
            recmp[a][b] = 1;
            return 1;
        }
        if(R[a] > mid && R[b] > mid){
            l = md + 1;
            cbound[a][0] = max(cbound[a][0], bound[mid][1]);
            cbound[b][0] = max(cbound[b][0], bound[mid][1]);
        }
        else {
            r = md - 1;
            cbound[a][1] = min(cbound[a][1], bound[mid][0]);
            cbound[b][1] = min(cbound[b][1], bound[mid][0]);
        }
    }
    assert(false);
    return 0;
}

bool cmp_subtask_4(int a, int b){
    fill(B, B+n, 0);
    B[a] = B[b] = n;
    playRound(B, R);
    return R[a] < R[b];
}

mt19937 rng_lmao(69420);

void allValues(int N, int W, int *P) {
    n = N;
    if (W == 2*N) {
        vector<int> vec(N);
        iota(vec.begin(), vec.end(), 0);
        stable_sort(vec.begin(), vec.end(), cmp_subtask_4);
        for(int i = 0; i < N; i++)P[vec[i]] = i+1;
    } else {
        for(int i = 0; i < N; i++)cbound[i][1] = 101;
        vector<int> vec(N);
        iota(vec.begin(), vec.end(), 0);
        stable_sort(vec.begin(), vec.end(), rng_lmao);
        sort(vec.begin(), vec.end(), cmp);
        for(int i = 0; i < N; i++)P[vec[i]] = i+1;
        
    }
}

implementer.cpp: In function ‘void grader()’:
implementer.cpp:138:11: warning: ignoring return value of ‘int fscanf(FILE*, const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  138 |     fscanf(fin, "%d %d %d",&F,&G,&maxQueries);
      |     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
implementer.cpp: In function ‘void runGame(int)’:
implementer.cpp:89:11: warning: ignoring return value of ‘int fscanf(FILE*, const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   89 |     fscanf(fin,"%d %d",&N,&W);
      |     ~~~~~~^~~~~~~~~~~~~~~~~~~
implementer.cpp:91:15: warning: ignoring return value of ‘int fscanf(FILE*, const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   91 |         fscanf(fin,"%d",&P[i]);
      |         ~~~~~~^~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/bits/stl_algobase.h:71,
                 from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from answer.code:2:
/usr/include/c++/13/bits/predefined_ops.h: In instantiation of ‘constexpr bool __gnu_cxx::__ops::_Iter_comp_iter<_Compare>::operator()(_Iterator1, _Iterator2) [with _Iterator1 = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Iterator2 = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>]’:
/usr/include/c++/13/bits/stl_algo.h:1819:14:   required from ‘constexpr void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253> >]’
/usr/include/c++/13/bits/stl_algo.h:2790:25:   required from ‘void std::__inplace_stable_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253> >]’
/usr/include/c++/13/bits/stl_algo.h:5045:28:   required from ‘void std::__stable_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253> >]’
/usr/include/c++/13/bits/stl_algo.h:5119:36:   required from ‘void std::stable_sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<int*, vector<int> >; _Compare = mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>]’
answer.code:145:20:   required from here
/usr/include/c++/13/bits/predefined_ops.h:158:30: error: no match for call to ‘(std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>) (int&, int&)’
  158 |         { return bool(_M_comp(*__it1, *__it2)); }
      |                       ~~~~~~~^~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/random:51,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:179:
/usr/include/c++/13/bits/random.h:587:7: note: candidate: ‘std::mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::result_type std::mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::operator()() [with _UIntType = long unsigned int; long unsigned int __w = 32; long unsigned int __n = 624; long unsigned int __m = 397; long unsigned int __r = 31; _UIntType __a = 2567483615; long unsigned int __u = 11; _UIntType __d = 4294967295; long unsigned int __s = 7; _UIntType __b = 2636928640; long unsigned int __t = 15; _UIntType __c = 4022730752; long unsigned int __l = 18; _UIntType __f = 1812433253; result_type = long unsigned int]’
  587 |       operator()();
      |       ^~~~~~~~
/usr/include/c++/13/bits/random.h:587:7: note:   candidate expects 0 arguments, 2 provided
/usr/include/c++/13/bits/predefined_ops.h: In instantiation of ‘constexpr bool __gnu_cxx::__ops::_Iter_comp_iter<_Compare>::operator()(_Iterator1, _Iterator2) [with _Iterator1 = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Iterator2 = int*; _Compare = std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>]’:
/usr/include/c++/13/bits/stl_algo.h:2300:14:   required from ‘void std::__move_merge_adaptive(_InputIt...