CSES - Putka Open 2020 – 3/5 - Results
Submission details
Task:Vaihdot
Sender:ollpu
Submission time:2020-10-16 18:23:19 +0300
Language:C++ (C++17)
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED35
#2ACCEPTED65
Test results
testverdicttimegroup
#1ACCEPTED0.02 s1, 2details
#2ACCEPTED0.11 s2details

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
for (int Ti = 0; Ti < T; ++Ti) {
int n;
cin >> n;
int t[n];
for (int i = 0; i < n; ++i) cin >> t[i];
if (n == 2) {
cout << (t[0] == 1 ? 0 : -1) << endl;
continue;
}
if (n == 3) {
if (t[1] != 2) {
cout << -1 << endl;
} else if (t[0] != 1) {
cout << "1\n1 3\n";
} else {
cout << "0\n";
}
continue;
}
vector<pair<int, int>> res;
for (int a = 0; a < n; ++a) {
if (t[a] == a+1) continue;
int b;
for (int j = a+1; j < n; ++j) {
if (t[j] == a+1) {
b = j;
break;
}
}
swap(t[a], t[b]);
if (a > b) swap(a, b);
if (b == a+1) {
if (a > 1) {
res.emplace_back(0, b);
res.emplace_back(0, a);
res.emplace_back(0, b);
} else if (b < n-2) {
res.emplace_back(b, n-1);
res.emplace_back(a, n-1);
res.emplace_back(b, n-1);
} else {
res.emplace_back(1, 3);
res.emplace_back(0, 2);
res.emplace_back(0, 3);
res.emplace_back(1, 3);
res.emplace_back(0, 2);
}
} else {
res.emplace_back(a, b);
}
}
cout << res.size() << endl;
for (auto [a, b] : res) cout << a+1 << " " << b+1 << endl;
}
}

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
1 58
2 45
3 16
4 29
...
Truncated