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

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define x first
#define y second
bool solve(int n, vector<int>& arr, vector<pii>& ans) {
vector<int> pos(n);
for (int i=0; i<n; i++)
pos[arr[i]] = i;
auto mv = [&](int i, int j) {
if (abs(i-j)<=1 || arr[i]==i) return;
swap(arr[i], arr[j]);
swap(pos[arr[i]], pos[arr[j]]);
ans.emplace_back(i, j);
};
for (int j=0; j<n; j++) {
int x = (j+1)%n;
mv(pos[x], x);
mv(pos[x], 0);
mv(pos[x], x);
mv(pos[x], n-1);
mv(pos[x], x);
if (arr[x] != x)
return false;
}
return true;
}
signed main() {
ios::sync_with_stdio(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> arr(n);
for (int i=0; i<n; i++) {
cin >> arr[i];
arr[i]--;
}
vector<pii> ans;
if (!solve(n, arr, ans))
cout << "-1\n";
else {
cout << ans.size() << '\n';
for (auto p : ans)
cout << p.x+1 << ' ' << p.y+1 << '\n';
}
}
}

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