# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
416667 | noshi91 | The Collection Game (BOI21_swaps) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <cstdint>
#include <vector>
namespace bitonic_sorter_impl {
using u32 = std::uint32_t;
std::vector<std::vector<std::pair<u32, u32>>> bitonic_sorter(const u32 n) {
std::vector<std::vector<std::pair<u32, u32>>> ret;
for (u32 w = 1; w < n; w *= 2) {
for (u32 s = w; s != 0; s /= 2) {
ret.push_back({});
bool rev = false;
for (u32 t = 0; t < n; t += 2 * w) {
for (u32 k = 0; k != 2 * w; k += 2 * s) {
for (u32 i = 0; i != s; i += 1) {
u32 a = t + k + i;
u32 b = t + k + i + s;
if (b < n) {
if (rev) {
ret.back().push_back({ b, a });
}
else {
ret.back().push_back({ a, b });
}
}
}
}
rev = !rev;
}
}
}
return ret;
}
} // namespace bitonic_sorter_impl
using bitonic_sorter_impl::bitonic_sorter;
#include <numeric>
#include <utility>
#include <swaps.h>
void solve(int N, int V) {
std::vector<int> a(N);
std::iota(a.begin(), a.end(), 0);
for (const auto &v : bitonic_sorter(N)) {
for (const auto &[a, b] : v) {
schedule(a + 1, b + 1);
}
const auto res = visit();
for (int i = 0; i != v.size(); i += 1) {
if (res[i]) {
std::swap(a[v[i].first], a[v[i].second]);
}
}
}
std::reverse(a.begin(), a.end());
for (auto& e : a) {
e += 1;
}
answer(a);
}