CSES - Putka Open 2020 – 3/5 - Results
Submission details
Task:Vaihdot
Sender:hltk
Submission time:2020-10-16 22:24:56 +0300
Language:C++ (C++17)
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED35
#2ACCEPTED65
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2details
#2ACCEPTED0.04 s2details

Code

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
void solve() {
int n;
cin >> n;
vector<int> v(n), pos(n);
for (int i = 0; i < n; ++i)
cin >> v[i], --v[i], pos[v[i]] = i;
vector<pair<int, int>> swaps;
auto do_swap = [&](int a, int b) {
swap(v[a], v[b]);
swap(pos[v[a]], pos[v[b]]);
swaps.emplace_back(a, b);
};
for (int i = 0; i < n; ++i) {
if (abs(pos[i] - i) == 0) continue;
else if (abs(pos[i] - i) > 1) do_swap(pos[i], i);
else {
for (int j = 0; j < n && pos[i] != i; ++j) {
if (abs(i - j) > 1 && abs(pos[i] - j) > 1) {
int u = pos[i];
do_swap(u, j);
do_swap(i, j);
do_swap(u, j);
}
}
if (pos[i] != i) {
for (int j = 0; j < n && pos[i] != i; ++j) {
if (abs(pos[i] - j) > 1) {
for (int k = j + 1; k < n && pos[i] != i; ++k) {
if (abs(j - k) > 1 && abs(i - k) > 1) {
int u = pos[i];
do_swap(j, u);
do_swap(j, k);
do_swap(i, k);
do_swap(j, k);
do_swap(j, u);
}
}
}
}
}
}
}
if (is_sorted(v.begin(), v.end())) {
cout << swaps.size() << '\n';
for (auto& [l, r] : swaps) cout << l+1 << ' ' << r+1 << '\n';
} else cout << -1 << '\n';
}
int main() {
int t;
cin >> t;
while (t--)
solve();
}

Test details

Test 1

Group: 1, 2

Verdict: ACCEPTED

input
1000
1
1
2
1 2
...

correct output
0
0
-1
0
-1
...

user output
0
0
-1
0
-1
...
Truncated

Test 2

Group: 2

Verdict: ACCEPTED

input
1000
79
49 42 77 41 37 61 46 55 7 72 4...

correct output
81
67 79
70 78
3 77
60 76
...

user output
83
58 1
45 2
16 3
29 4
...
Truncated