//
// --- 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 <bits/stdc++.h>
#include <ranges>
using namespace std;
// schedule(i, j) == 1 ==> a[i] >= a[j] at the time of visit
pair<vector<int>, vector<int>> split(vector<int> v) {
int len = v.size();
vector<int> L(v.begin(), v.begin() + len/2), R(v.begin() + len/2, v.end());
return {L, R};
}
struct Sorter {
// rooms is the currently known permutation, in ascending order
map<int, vector<pair<int, int>>> network;
int n, n_padded;
void place_in_round(int round, int i, int j) {
network[round].emplace_back(i, j);
cerr << "!! scheduled " << i << " " << j << " in round " << round << endl;
}
// all of these functions return the round after these swaps finish
int sort_arbitrary(int round, vector<int> rooms) {
int len = rooms.size();
if (len <= 1) return round;
vector<int> L(rooms.begin(), rooms.begin() + len/2), R(rooms.begin() + len/2, rooms.end());
int round_after = sort_arbitrary(round, L);
int _ = sort_arbitrary(round, R);
return merge(round_after, L, R);
}
int merge(int round, vector<int> l, vector<int> r) {
cerr << "!! merge " << l.size() << endl;
int len = l.size();
assert(l.size() == r.size());
for (int i = 0; i < len; ++i) place_in_round(round, l[i], r[len - 1 - i]);
// after this round, the circuit places all lower elements in r and upper elements in l
cerr << " starting layer " << 2 * l.size() << " merge " << endl;
int merge_until = sort_vshaped(round + 1, r);
cerr << " layer " << 2 * l.size() << " merge from " << round + 1 << " until " << merge_until << endl;
return sort_vshaped(round + 1, l);
}
// sort a zigzag such that first-(inflection1) and (inflection2)-last do not overlap
int sort_zigzag(int round, vector<int> rooms) {
return sort_vshaped(round, rooms);
// int len = rooms.size();
// if (len <= 1) return round;
// for (int i = 0; i < len/2; ++i) place_in_round(round, rooms[i], rooms[len - 1 - i]);
// auto [L, R] = split(rooms);
// sort_vshaped(round + 1, L);
// return sort_vshaped(round + 1, R);
//
}
// sort rooms, assuming it is descending/ascending
int sort_vshaped(int round, vector<int> rooms) {
cerr << "sort_vshaped " << round << " " << rooms.size() << endl;
// this is mental illness
int len = rooms.size();
if (len <= 1) return round;
for (int i = 0; i < len/2; ++i) place_in_round(round, rooms[i], rooms[i+len/2]);
// after this, the upper elements are all in the first half, the lower elements are all in the second half
auto [L, R] = split(rooms);
sort_zigzag(round + 1, L);
return sort_zigzag(round + 1, R);
}
Sorter(int N) : n(N), n_padded(1 << (32 - __builtin_clz(N - 1))) {
// we create a set of visits that can solve the 60%, and use that to solve the 100%
vector<int> rooms(n_padded);
iota(begin(rooms), end(rooms), 0);
sort_arbitrary(0, rooms);
}
vector<int> sort() {
vector<int> labels(n_padded); iota(begin(labels), end(labels), 1);
for (auto [round_id, swaps] : network) {
int swaps_made = 0;
vector<int> source(swaps.size(), -1);
for (int qid = 0; qid < swaps.size(); ++qid) {
auto [i, j] = swaps[qid];
if (labels[i] <= n && labels[j] <= n) {
source[qid] = swaps_made++;
schedule(labels[i], labels[j]);
}
}
vector<int> answers = visit();
for (int qid = 0; qid < swaps.size(); ++qid) {
auto [i, j] = swaps[qid];
if (source[qid] != -1) {
if (answers[source[qid]] == 0) swap(labels[i], labels[j]);
} else {
if (labels[i] <= n) swap(labels[i], labels[j]);
}
}
cerr << "! round " << round_id << " state:";
for (int v : labels) cerr << " " << v;
cerr << endl;
}
vector<int> ans;
for (int v : labels) if (v <= n) ans.push_back(v);
return ans;
}
};
// # [INPUT] expected: [7, 12, 16, 2, 10, 6, 1, 4, 14, 15, 9, 11, 5, 3, 13, 8]
void solve(int N, int V) {
// 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});
auto sorter = Sorter(N);
auto rooms = sorter.sort();
// reverse(begin(rooms), end(rooms));
answer(rooms);
}
