| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 416681 | 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 <numeric>
#include <vector>
namespace bitonic_sorter_impl {
using u32 = std::uint32_t;
std::vector<std::vector<std::pair<u32, u32>>> bitonic_sorter(const u32 n) {
u32 m = 1;
while (m < n) {
m *= 2;
}
std::vector<u32> map(m);
std::iota(map.begin(), map.end(), static_cast<u32>(0));
std::vector<std::vector<std::pair<u32, u32>>> ret;
const auto push = [&](const u32 x, const u32 y) {
if (map[y] >= n) {
return;
}
if (map[x] < n) {
ret.back().push_back({map[x], map[y]});
} else {
std::swap(map[x], map[y]);
}
};
for (u32 w = 1; w != m; w *= 2) {
for (u32 s = w; s != 0; s /= 2) {
ret.push_back({});
bool rev = false;
for (u32 t = 0; t != m; 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 (rev) {
push(b, a);
} else {
push(a, b);
}
}
}
rev = !rev;
}
}
}
return ret;
}
} // namespace bitonic_sorter_impl
using bitonic_sorter_impl::bitonic_sorter;
#include <algorithm>
#include <numeric>
#include <utility>
#ifdef ONLINE_JUDGE
#include <swaps.h>
#else
#include <cassert>
#include <iostream>
void solve(int, int);
int j_N = 5;
std::vector<int> j_A = {0, 4, 3, 1, 2};
std::vector<std::pair<int, int>> j_buf;
int main() {
solve(j_N, 0);
return 0;
}
void schedule(int i, int j) {
assert(1 <= i && i <= j_N);
assert(1 <= j && j <= j_N);
assert(i != j);
j_buf.push_back({i - 1, j - 1});
}
std::vector<int> visit() {
std::vector<int> ret;
for (const auto &[i, j] : j_buf) {
ret.push_back(j_A[i] > j_A[j]);
}
j_buf.clear();
return ret;
}
void answer(std::vector<int> r) {
for (const auto &e : r) {
std::cout << e - 1 << " ";
}
std::cout << "\n";
}
#endif
void solve(int N, int) {
std::vector<int> a(N);
std::iota(a.begin(), a.end(), 0);
for (const auto &v : bitonic_sorter(N)) {
for (const auto &[x, y] : v) {
schedule(a[x] + 1, a[y] + 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);
}