Task: | Vaihdot |
Sender: | Mahtimursu |
Submission time: | 2020-10-16 20:42:50 +0300 |
Language: | C++ (C++11) |
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 <bits/stdc++.h> typedef long long ll; #define M 1000000007 using namespace std; void test_case() { int n; cin >> n; vector<int> v(n+1); for (int i = 1; i <= n; ++i) { cin >> v[i]; } vector<pair<int, int>> res; if (n == 4) { // brutetaan n=4 if (v[1] == 4 && v[2] == 1 && v[3] == 2 && v[4] == 3) { swap(v[1], v[4]); res.push_back({1, 4}); } if (v[1] == 3 && v[2] == 4 && v[3] == 2 && v[4] == 1) { swap(v[1], v[4]); res.push_back({1, 4}); } else if (v[1] == 3 && v[2] == 1 && v[3] == 2 && v[4] == 4) { swap(v[2], v[4]); res.push_back({2, 4}); } else if (v[1] == 2 && v[2] == 4 && v[3] == 1 && v[4] == 3) { swap(v[2], v[4]); res.push_back({2, 4}); } else if (v[1] == 1 && v[2] == 3 && v[3] == 2 && v[4] == 4) { swap(v[1], v[3]); res.push_back({1, 3}); } if (v[1] == 1 && v[2] == 4 && v[3] == 2 && v[4] == 3) { res.push_back({1, 3}); res.push_back({1, 4}); res.push_back({1, 3}); res.push_back({2, 4}); cout << res.size() << "\n"; for (auto val : res) { cout << val.first << " " << val.second << "\n"; } return; } else if (v[1] == 2 && v[2] == 3 && v[3] == 1 && v[4] == 4) { res.push_back({2, 4}); res.push_back({1, 4}); res.push_back({1, 3}); res.push_back({2, 4}); cout << res.size() << "\n"; for (auto val : res) { cout << val.first << " " << val.second << "\n"; } return; } else if (v[1] == 4 && v[2] == 3 && v[3] == 2 && v[4] == 1) { res.push_back({1, 3}); res.push_back({1, 4}); res.push_back({2, 4}); res.push_back({1, 4}); res.push_back({1, 3}); res.push_back({1, 4}); cout << res.size() << "\n"; for (auto val : res) { cout << val.first << " " << val.second << "\n"; } return; } } map<int, int> where; for (int i = 1; i <= n; ++i) { where[v[i]] = i; } // locate 1 by 1 for (int i = 1; i <= n; ++i) { int location = where[i]; //cout << "at: " << i << " num is at: " << location << endl; if (location == i) continue; // helppo if (location - i > 1) { v[location] = v[i]; where[v[i]] = location; v[i] = i; res.push_back({i, location}); } else { // vieressä if (i > 2) { res.push_back({1, location}); res.push_back({1, i}); res.push_back({1, location}); } else if (i < n - 2) { res.push_back({location, n}); res.push_back({i, n}); res.push_back({location, n}); } else { cout << -1 << endl; return; } v[location] = v[i]; where[v[i]] = location; v[i] = i; } } // VASTAUS cout << res.size() << "\n"; for (auto val : res) { cout << val.first << " " << val.second << "\n"; } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); int t; cin >> t; for (int i = 0; i < t; ++i) { test_case(); //cout << "\n"; } return 0; } /*unsigned int sz = res.size(); while (true) { for (int i = 0; i < n; ++i) { if (v[i] == i + 1) continue; // oikea int id = v[i]; if (abs(id - i - 1) == 1) continue; int tg = v[id-1]; v[id-1] = v[i]; v[i] = tg; res.push_back({i+1, id}); } if (sz == res.size()) break; sz = res.size(); } if (!is_sorted(v.begin(), v.end())) { if (n < 4) { cout << -1 << "\n"; return; } for (int i = 0; i < n-1; ++i) { if (v[i] == i + 1) continue; // Use first if (i >= n - 2) { res.push_back({1, i+1}); res.push_back({1, i+2}); res.push_back({1, i+1}); v[i] = i + 1; v[i + 1] = i + 2; } else { // use last res.push_back({i+1, n}); res.push_back({i+2, n}); res.push_back({i+1, n}); v[i] = i + 1; v[i + 1] = i + 2; } } }*/
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 |