//
// --- 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 <algorithm>
#include <iostream>
#include <cassert>
using namespace std;
void get_stree_nodes(int d, int l, int r, vector<vector<pair<int, int>>>& ans) {
if (r - l == 1)
return;
if (d >= ans.size())
ans.push_back({});
ans[d].push_back({l, r});
int m = (l + r) / 2;
get_stree_nodes(d + 1, l, m, ans);
get_stree_nodes(d + 1, m, r, ans);
}
void solve(int N, int V) {
vector<int> v(N);
for (int i = 0; i < N; ++i)
v[i] = i + 1;
vector<vector<pair<int, int>>> nds;
get_stree_nodes(0, 0, N, nds);
for (int d = nds.size() - 1; d >= 0; --d) {
vector<pair<pair<int, int>, pair<int, int>>> sgs;
for (auto [l, r] : nds[d]) {
int m = (l + r) / 2;
sgs.push_back({{l, m}, {m, r}});
}
// cout << endl;
for (auto& [s1, s2] : sgs) {
if (s2.second - s2.first != s1.second - s1.first) {
assert(s2.second - s2.first - 1 == s1.second - s1.first);
--s2.second;
// cout << "(" << s1.first << ' ' << s1.second << ' ' << s2.first << ' ' << s2.second << ") ";
}
}
// cout << endl;
bool cont = true;
while (cont) {
cont = false;
for (auto [s1, s2] : sgs) {
if (s2.second <= s2.first)
continue;
cont = true;
for (int i = 0; i < s2.second - s2.first; ++i)
schedule(v[s1.first + i], v[s2.first + i]);
}
if (!cont)
break;
vector<int> vis = visit();
int visi = 0;
for (auto& [s1, s2] : sgs) {
if (s2.second <= s1.first)
continue;
for (int i = 0; i < s2.second - s2.first; ++i) {
if (!vis[visi++])
swap(v[s1.first + i], v[s2.first + i]);
}
++s1.first;
--s2.second;
}
}
vector<pair<int, int>> leftover;
for (auto& p : nds[d]) {
if ((p.second - p.first) % 2) {
leftover.push_back({p.first, p.second - 1});
}
else
leftover.push_back({-1, -1});
}
while (true) {
bool isleft = false;
for (auto x : leftover) {
isleft |= x.first < x.second;
}
if (!isleft)
break;
for (size_t i = 0; i < leftover.size(); ++i) {
if (leftover[i].first >= leftover[i].second)
continue;
schedule(v[leftover[i].first], v[leftover[i].second]);
}
vector<int> vis = visit();
int visi = 0;
for (size_t i = 0; i < leftover.size(); ++i) {
if (leftover[i].first >= leftover[i].second)
continue;
if (!vis[visi++])
swap(v[leftover[i].first], v[leftover[i].second]);
++leftover[i].first;
}
}
}
answer(v);
}
