//
// --- Sample implementation for the task swaps ---
//
// To compile this program with the sample grader, place:
// swaps.h swaps_sample.cpp sample_grader.cpp
// in a single folder and run:
// g++ swaps_sample.cpp sample_grader.cpp
// in this folder.#include <bits/stdc++.h>
#include <bits/stdc++.h>
#include "swaps.h"
using namespace std;
template<class T, class U>
void ckmin(T &a, U b)
{
if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
if (a < b) a = b;
}
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
int N, Q;
vpi cand;
vi ans;
vi work()
{
if (cand.empty()) return vector<int>();
for (pii p : cand)
{
schedule(p.fi + 1, p.se + 1);
}
cand.clear();
return visit();
}
int find_winner(vi v)
{
if (SZ(v) == 1)
{
return v[0];
}
vi lol;
for (int i = 1; i < SZ(v); i += 2)
{
cand.PB({v[i - 1], v[i]});
}
auto res = work();
FOR(i, 0, SZ(res))
{
lol.PB(v[2 * i + 1 - res[i]]);
}
if (SZ(v) & 1) lol.PB(v.back());
return find_winner(lol);
}
void solve(int n, int q)
{
N = n; Q = q;
//try to figure out which one allows more?
if (Q >= 5000)
{
vi nums(N); iota(ALL(nums), 0);
FOR(i, 0, N)
{
int x = find_winner(nums);
ans.PB(x);
nums.erase(find(ALL(nums), x));
}
for (int &x : ans)
{
x++;
}
answer(ans);
}
//always move (i...j)
//????
for (int i = (1 << 31 - __builtin_clz(N)); i; i >>= 1)
{
FOR(j, 0, N - i)
{
if (j % (2 * i) < i)
{
cand.PB({j, j + i});
}
}
work();
FOR(j, 0, N - i)
{
if (j % (2 * i) >= i)
{
cand.PB({j, j + i});
}
}
work();
FOR(j, 0, N - i)
{
if (j % (2 * i) < i)
{
cand.PB({j, j + i});
}
}
work();
}
ans.resize(N);
iota(ALL(ans), 1);
answer(ans);
return;
// TODO implement this function
// schedule(1, 2);
// std::vector<int> v = visit();
// if (v[0] == 1)
// answer({1, 2, 3, 4});
// else
// answer({2, 1, 3, 4});
}
