#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;
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];
};
for (int i = 0; i < 1000; i++) {
int l = rnd() % n;
int r = rnd() % n;
if (l == r) continue;
ans.emplace_back(l, r);
a[l] ^= a[r];
}
std::vector<int> bad;
auto unique = [&]() {
// return std::set<int>(a.begin(), a.end()).size() == n;
std::map<int, std::vector<int>> m;
for (int i = 0; i < n; i++) {
m[a[i]].push_back(i);
}
bad.clear();
for (auto [x, y] : m) {
if (y.size() > 1) {
for (auto t : y) bad.push_back(t);
}
}
return bad.empty();
};
while (!unique()) {
int l = rnd() % n;
int r = rnd() % n;
if (l == r) continue;
ans.emplace_back(l, r);
a[l] ^= a[r];
}
std::vector<int> b = a;
std::sort(b.begin(), b.end());
if (S == 1) {
for (int i = 0; i < n; i++) {
for (int j = n - 1; j >= 0; j--) {
if (a[j] != b[j]) {
int pos = std::find(a.begin(), a.end(), b[j]) - a.begin();
for (; pos < j; pos++) {
swap(pos, pos + 1);
}
}
}
}
}
std::cout << ans.size() << "\n";
for (auto [i, j] : ans) {
std::cout << i + 1 << " " << j + 1 << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Not adjacent |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Not adjacent |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Not adjacent |
| 2 |
Halted |
0 ms |
0 KB |
- |
