CSES - Putka Open 2020 – 3/5 - Results
Submission details
Task:Vaihdot
Sender:Laakeri
Submission time:2020-10-17 16:25:17 +0300
Language:C++ (C++11)
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;
int a[111];
void solve() {
int n;
cin>>n;
for (int i=1;i<=n;i++){
cin>>a[i];
}
if (n==1) {
cout<<0<<endl;
return;
}
if (n==2) {
if (a[1] == 1) {
cout<<0<<endl;
} else {
cout<<-1<<endl;
}
return;
}
if (n==3) {
if (a[2] != 2) {
cout<<-1<<endl;
} else {
if (a[1] == 1) {
cout<<0<<endl;
} else {
cout<<1<<endl;
cout<<"1 3"<<endl;
}
}
return;
}
vector<pair<int, int>> ans;
for (int i=1;i<=n;i++){
for (int j=1;j<i;j++){
assert(a[j] == j);
}
if (a[i] == i) continue;
int p=0;
for (int j=i+1;j<=n;j++){
if (a[j] == i) {
p=j;
}
}
assert(p && a[p] == i);
if (p>i+1){
ans.push_back({i, p});
swap(a[i], a[p]);
continue;
}
if (p+1<n){
ans.push_back({p, n});
ans.push_back({n, i});
swap(a[p], a[n]);
swap(a[n], a[i]);
} else if (p+1==n) {
ans.push_back({p, 1});
ans.push_back({1, n});
ans.push_back({n, i});
ans.push_back({p, 1});
swap(a[p], a[1]);
swap(a[1], a[n]);
swap(a[n], a[i]);
swap(a[p], a[1]);
} else {
swap(a[n], a[1]);
swap(a[1], a[n-1]);
swap(a[n], a[1]);
ans.push_back({a[n], a[1]});
ans.push_back({a[1], a[n-1]});
ans.push_back({a[n], a[1]});
}
}
for (int i=1;i<=n;i++){
assert(a[i] == i);
}
cout<<ans.size()<<'\n';
for (auto x : ans){
cout<<x.first<<" "<<x.second<<'\n';
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int tcs;
cin>>tcs;
for (int tc=1;tc<=tcs;tc++){
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
1 58
2 45
3 16
4 29
...
Truncated