Task: | Vaihdot |
Sender: | AtskaFin |
Submission time: | 2020-10-18 16:56:33 +0300 |
Language: | C++ (C++17) |
Status: | READY |
Result: | 0 |
group | verdict | score |
---|---|---|
#1 | WRONG ANSWER | 0 |
#2 | WRONG ANSWER | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | WRONG ANSWER | 0.01 s | 1, 2 | details |
#2 | ACCEPTED | 0.04 s | 2 | details |
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] varastonaint varasto = v[n-1];// eka vaihtov[n-1] = v[i];v[i] = varasto;//s.push_back({ n, i+1});saveSwap(n, i+1);// toinen vaihtovarasto = v[x-1];v[x-1] = v[n-1];v[n-1] = varasto;//s.push_back({ n, x });saveSwap(n, x);// kolmas vaihtovarasto = 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] varastonaint varasto = v[0];// eka vaihtov[0] = v[i];v[i] = varasto;//s.push_back({ 1, i+1 });saveSwap(1, i+1);// toinen vaihtovarasto = v[x-1];v[x-1] = v[0];v[0] = varasto;//s.push_back({ 1, x });saveSwap(1, x);// kolmas vaihtovarasto = 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: WRONG ANSWER
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 |