Submission #465591

#TimeUsernameProblemLanguageResultExecution timeMemory
465591kilikumaXor Sort (eJOI20_xorsort)C++14
65 / 100
11 ms1272 KiB
#include <bits/stdc++.h> std::mt19937 rnd(std::chrono::steady_clock::now().time_since_epoch().count()); int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, S; std::cin >> n >> S; std::vector<int> a(n); for (int i = 0; i < n; i++) { std::cin >> a[i]; } std::vector<std::pair<int, int>> ans; if (S == 1) { auto swap = [&](int i, int j) { ans.emplace_back(i, j); ans.emplace_back(j, i); ans.emplace_back(i, j); a[i] ^= a[j]; a[j] ^= a[i]; a[i] ^= a[j]; }; while (!std::is_sorted(a.begin(), a.end())) { for (int j = 1; j < n; j++) { if (a[j - 1] > a[j]) { swap(j - 1, j); } } } } else { auto swap = [&](int i, int j) { ans.emplace_back(i, j); ans.emplace_back(j, i); a[i] ^= a[j]; a[j] ^= a[i]; }; for (int i = 19; i >= 0; i--) { for (int j = 0; j < n - 1; j++) { if (a[j] >> i & 1) { if (a[j + 1] >> i & 1) { ans.emplace_back(j, j + 1); a[j] ^= a[j + 1]; } else { swap(j + 1, j); } } } if (a[n - 1] >> i & 1) n--; } } std::cout << ans.size() << "\n"; for (auto [i, j] : ans) { std::cout << i + 1 << " " << j + 1 << "\n"; } return 0; }

Compilation message (stderr)

xorsort.cpp: In function 'int main()':
xorsort.cpp:58:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |     for (auto [i, j] : ans) {
      |               ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...