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

Code

#include <iostream>
#include <vector>
using namespace std;
int v[128];
vector<pair<int,int>> res;
void addSwap(int a, int b) {
	res.emplace_back(a,b);
	swap(v[a],v[b]);
}
int main() {
	int t;cin>>t;
	while(t--){
		int n;cin>>n;
		res.clear();
		for(int i=0;i<n;++i)cin>>v[i],--v[i];
		for(int i=0;i<n;){
			int x = v[i];
			if (x==i) {
				i++;
			} else if (x==i-1 || x==i+1) {
				int a = min(x,i), b = max(x,i);
				int t = a-2;
				if (t<0) t = b+2;
				if (t>=n) {
					if (a>0 && b<n-1) {
						addSwap(b,0);
						addSwap(a,n-1);
						addSwap(0,n-1);
						addSwap(b,0);
						addSwap(a,n-1);
						continue;
					} else {
						cout<<"-1\n";
						goto next;
					}
				}
				addSwap(a,t);
				addSwap(b,t);
				addSwap(a,t);
			} else {
				addSwap(x,i);
			}
		}
		cout<<res.size()<<'\n';
		for(auto [a,b]: res) cout<<a+1<<' '<<b+1<<'\n';
next:;
	}
}

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
...

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
49 1
10 1
72 1
38 1
...