CSES - Putka Open 2020 – 3/5 - Results
Submission details
Task:Vaihdot
Sender:AtskaFin
Submission time:2020-10-18 16:56:33 +0300
Language:C++ (C++17)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
Test results
testverdicttimegroup
#10.01 s1, 2details
#2ACCEPTED0.04 s2details

Code

#include <iostream>
#include <vector>
using namespace std;
int t;
int n;
vector<int> v;
vector<pair<int, int>> s;
bool isSorted() {
int x = v[0];
for (int i = 1; i < n; i++) {
if (v[i] < x) return false;
else x = v[i];
}
return true;
}
void saveSwap(int a, int b) {
if (!s.size()) {
s.push_back({ a, b });
return;
}
pair<int, int> last = s[s.size()-1];
if (
(last.first == a && last.second == b) ||
(last.second == a && last.first == b)
) {
s.pop_back();
} else {
s.push_back({ a, b });
}
}
void runSort() {
if (isSorted()) return;
s.clear();
int x = 1;
do {
if (v[x-1] != x) {
for (int i = n-1; i > -1; i--) {
if (v[i] == x) {
if (i == x) {
if (i < n-2) {
// käytetään v[n-1] varastona
int varasto = v[n-1];
// eka vaihto
v[n-1] = v[i];
v[i] = varasto;
//s.push_back({ n, i+1});
saveSwap(n, i+1);
// toinen vaihto
varasto = v[x-1];
v[x-1] = v[n-1];
v[n-1] = varasto;
//s.push_back({ n, x });
saveSwap(n, x);
// kolmas vaihto
varasto = v[i];
v[i] = v[n-1];
v[n-1] = varasto;
//s.push_back({ n, i+1 });
saveSwap(n, i+1);
} else if (x > 2) {
// käytetään v[0] varastona
int varasto = v[0];
// eka vaihto
v[0] = v[i];
v[i] = varasto;
//s.push_back({ 1, i+1 });
saveSwap(1, i+1);
// toinen vaihto
varasto = v[x-1];
v[x-1] = v[0];
v[0] = varasto;
//s.push_back({ 1, x });
saveSwap(1, x);
// kolmas vaihto
varasto = v[i];
v[i] = v[0];
v[0] = varasto;
//s.push_back({ i+1, 1 });
saveSwap(i+1, 1);
}
} else {
int varasto = v[x-1];
v[x-1] = x;
v[i] = varasto;
//s.push_back({ i+1, x });
saveSwap(i+1, x);
}
//for (int i : v) cout << i << " ";
//cout << endl;
break;
}
}
}
x++;
//for (int i : v) cout << i << " ";
//cout << endl;
} while (!isSorted());
}
bool isPossible() {
if (n == 1) {
return true;
}
if (n == 2) {
if (v[0] == 1) return true;
else return false;
}
if (n == 3) {
if (v[1] == 2) return true;
else return false;
}
if (n == 4) {
if (v[1] != 2 && v[2] != 3) return false;
else return true;
}
return true;
}
int main() {
//ios_base::sync_with_stdio(0);
//cin.tie(0);
cin >> t;
for (int i = 0; i < t; i++) {
cin >> n;
v.clear();
v.resize(n);
for (int& i : v) cin >> i;
if (isPossible()) {
runSort();
if ((int)s.size() > n*5) {
cout << "-1\n";
} else {
cout << s.size() << "\n";
for (pair<int, int> p : s) {
if (p.first > p.second) {
cout << p.second << " " << p.first << "\n";
} else {
cout << p.first << " " << p.second << "\n";
}
}
}
//for (int i : v) cout << i << " ";
} else {
cout << "-1\n";
}
}
}

Test details

Test 1

Group: 1, 2

Verdict:

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