CSES - Putka Open 2020 – 3/5 - Results
Submission details
Task:Vaihdot
Sender:tsiki2
Submission time:2020-10-18 21:00:05 +0300
Language:C++11
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED35
#2ACCEPTED65
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2details
#2ACCEPTED0.05 s2details

Compiler report

input/code.cpp: In function 'bool is_sorted(std::vector<int>&)':
input/code.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < v.size(); i++) {
                  ~~^~~~~~~~~~
input/code.cpp: In function 'int get_idx(int)':
input/code.cpp:39:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < curvec.size(); i++) {
                  ~~^~~~~~~~~~~~~~~
input/code.cpp:42:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Code

#include <stdio.h> // include before iostream for faster scanf
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <utility>
#include <set>
#include <unordered_set>
#include <cmath>
#include <math.h>
#include <queue>
#include <stdlib.h>
#include <string.h>
#include <sstream>
#include <tuple>
#include <utility>
#include <iomanip>
#include <iterator>

using namespace std;
typedef long long LL;

#define printv(printVec) for (auto printVecIter : (printVec)) cout << printVecIter << " "; cout << endl;

// g++ -Wall -Wshadow -std=c++11 a.cpp && ./a.out
vector<pair<int,int>> ans;
vector<int> curvec;

bool is_sorted(vector<int> & v) {
	for (int i = 1; i < v.size(); i++) {
		if (v[i] < v[i-1]) return false;
	}
	return true;
}

int get_idx(int item) {
	for (int i = 0; i < curvec.size(); i++) {
		if (item == curvec[i]) return i;
	}
}

void sw(int i1, int i2) {
	ans.push_back({i1+1, i2+1});
	swap(curvec[i1], curvec[i2]);
}


int main() {
	std::ios::sync_with_stdio(false);cin.tie(0);
	int t; cin>>t;
	while (t--) {
		int n; cin>>n;
		vector<int> inp(n);
		ans = {};
		for (int i =0;i<n;i++) {
			cin>>inp[i];
		}
		curvec = inp;
		if (curvec.size() <= 2) {
			if (is_sorted(curvec)) {
				cout << 0 << "\n";
			} else {
				cout << -1 << "\n";
			}
			continue;
		}
		if (curvec.size() == 3) {
			if (!is_sorted(curvec)) {
				swap(curvec[0], curvec[2]);
				if (is_sorted(curvec)) {
					cout << 1 << "\n";
					cout << 1 << " " << 3 << "\n";
				} else {
					cout << -1 << "\n";
				}
			} else {
				cout << 0 << "\n";
			}
			continue;
		}

		int two = get_idx(2);
		if (two == 0) {
			sw(0, 3);
			sw(1, 3);
		} else if (two == 2) {
			sw(0, 2);
			sw(0, 3);
			sw(1, 3);
		} else if (two > 2) {
			sw(1, two);
		}

		int one = get_idx(1);
		if (one >= 2) {
			sw(0, one);
		}

		for (int i = 0; i < n; i++) {
			int idx = i+1;
			if (curvec[i] == i + 1) continue; // already in place
			while (curvec[idx] != i+1) idx++;
			sw(0, idx);
			sw(i, 0);
			sw(0, idx);
		}
		// cout << "AA " << endl;
		cout << ans.size() << "\n";
		for (auto p : ans) {
			cout << p.first << " " << p.second << "\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
...

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
221
2 45
1 58
1 16
3 1
...