//
// --- 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 "swaps.h"
#include <iostream>
#include <vector>
#include <set>
using namespace std;
#define pb push_back
#define eb emplace_back
using ii = pair<int, int>;
int N, n0;
vector<ii> cmps;
void cmp(int x, int y) {
if (x >= N || y >= N) return;
cmps.eb(x, y);
}
void merge(vector<int> v) {
if (v.size() == 2) {
cmp(v[0], v[1]);
return;
}
vector<int> even, odd;
for (int i = 0; i < (int)v.size(); i++) {
if (i % 2 == 0) even.pb(v[i]);
else odd.pb(v[i]);
}
merge(even);
merge(odd);
for (int i = 1; i + 1 < (int)v.size(); i += 2) {
cmp(v[i], v[i + 1]);
}
}
void sort(vector<int> v) {
if (v.size() == 2) {
cmp(v[0], v[1]);
return;
}
int m = (int)v.size() / 2;
sort(vector<int>(v.begin(), v.begin() + m));
sort(vector<int>(v.begin() + m, v.end()));
merge(v);
}
void solve(int N, int V) {
::N = N;
n0 = 1;
while (n0 < N) {
n0 <<= 1;
}
vector<int> tmp;
for (int i = 0; i < n0; i++) {
tmp.pb(i);
}
sort(tmp);
vector<int> Q, x, y;
set<int> ss;
for (int i = 1; i <= N; i++) {
Q.pb(i - 1);
}
for (auto [a, b] : cmps) {
if (ss.find(Q[a] + 1) != ss.end() || ss.find(Q[b] + 1) != ss.end()) {
auto ret = visit();
for (int l = 0; l < (int)ret.size(); l++) {
if (!ret[l]) {
swap(Q[x[l]], Q[y[l]]);
}
}
x.clear();
y.clear();
ss.clear();
}
x.pb(a);
y.pb(b);
ss.insert(Q[a] + 1);
ss.insert(Q[b] + 1);
schedule(Q[a] + 1, Q[b] + 1);
}
auto ret = visit();
for (int l = 0; l < (int)ret.size(); l++) {
if (!ret[l]) {
swap(Q[x[l]], Q[y[l]]);
}
}
for (int &i : Q) i++;
answer(Q);
}
