#include <bits/stdc++.h> using namespace std; const int N = 3005; int n; int tab[N]; bitset<N> vis; vector<vector<pair<int, int> > > res; void rescale() { vector<int> kub(N + 1); for (int i = 1; i <= n; i++) { kub[tab[i]] = 1; } for (int i = 1; i <= N; i++) { kub[i] += kub[i - 1]; } for (int i = 1; i <= n; i++) { tab[i] = kub[tab[i]]; } } void check() { vis.reset(); res.emplace_back(); for (int i = 1; i <= n; i++) { if (!vis[i]) { vector<int> cycle; int x = i; while (!vis[x]) { vis[x] = true; cycle.push_back(x); x = tab[x]; } // cout << "siema "; // for (int v : cycle) { // cout << v << " "; // } // cout << endl; for (int i = 0; i < (int) cycle.size(); i++) { int ind1 = cycle[i]; int ind2 = cycle[cycle.size() - i - 1]; if (vis[ind1] && vis[ind2] && ind1 != ind2) { res.back().push_back({ind1, ind2}); swap(tab[ind1], tab[ind2]); vis[ind1] = vis[ind2] = false; } } for (int v : cycle) { vis[v] = true; } } } } bool make_inv() { vis.reset(); res.emplace_back(); for (int i = 1; i <= n; i++) { if (tab[i] == i || vis[i]) { continue; } if (tab[tab[i]] != i) { res.pop_back(); return false; } res.back().push_back({i, tab[i]}); // swap(tab[i], tab[tab[i]]); vis[i] = vis[tab[i]] = true; } if (res.back().empty()) { res.pop_back(); } return true; } // bool inc_res() { // res.emplace_back(); // vis.reset(); // for (int i = 1; i <= n; i++) { // if (!vis[i]) { // int x = i; // while (!vis[x]) { // vis[x] = true; // if (!vis[tab[x]]) { // vis[tab[i]] = true; // res.back().push_back({x, tab[x]}); // swap(tab[x], tab[tab[x]]); // } // x = tab[x]; // } // } // } // // for (int i = 1; i <= n; i++) { // // if (tab[i] != i && !vis[i] && !vis[tab[i]]) { // // vis[i] = vis[tab[i]] = true; // // res.back().push_back({i, tab[i]}); // // swap(tab[i], tab[tab[i]]); // // } // // } // // for (int i = 1; i <= n; i++) { // // cout << tab[i] << " "; // // } // // cout << endl; // return !res.back().empty(); // } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) { cin >> tab[i]; } rescale(); // while (inc_res()) {} if (!make_inv()) { check(); make_inv(); } // cout << "witam "; // for (int i = 1; i <= n; i++) { // cout << tab[i] << " "; // } // cout << endl; // cout << "siema " << endl; cout << res.size() << "\n"; for (auto &vec : res) { if (vec.empty()) { break; } cout << 2 * vec.size() << "\n"; for (int i = 0; i < (int) vec.size(); i++) { cout << vec[i].first << " "; } for (int i = (int) vec.size() - 1; i >= 0; i--) { cout << vec[i].second << " "; } cout << "\n"; } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 | #include <bits/stdc++.h> using namespace std; const int N = 3005; int n; int tab[N]; bitset<N> vis; vector<vector<pair<int, int> > > res; void rescale() { vector<int> kub(N + 1); for (int i = 1; i <= n; i++) { kub[tab[i]] = 1; } for (int i = 1; i <= N; i++) { kub[i] += kub[i - 1]; } for (int i = 1; i <= n; i++) { tab[i] = kub[tab[i]]; } } void check() { vis.reset(); res.emplace_back(); for (int i = 1; i <= n; i++) { if (!vis[i]) { vector<int> cycle; int x = i; while (!vis[x]) { vis[x] = true; cycle.push_back(x); x = tab[x]; } // cout << "siema "; // for (int v : cycle) { // cout << v << " "; // } // cout << endl; for (int i = 0; i < (int) cycle.size(); i++) { int ind1 = cycle[i]; int ind2 = cycle[cycle.size() - i - 1]; if (vis[ind1] && vis[ind2] && ind1 != ind2) { res.back().push_back({ind1, ind2}); swap(tab[ind1], tab[ind2]); vis[ind1] = vis[ind2] = false; } } for (int v : cycle) { vis[v] = true; } } } } bool make_inv() { vis.reset(); res.emplace_back(); for (int i = 1; i <= n; i++) { if (tab[i] == i || vis[i]) { continue; } if (tab[tab[i]] != i) { res.pop_back(); return false; } res.back().push_back({i, tab[i]}); // swap(tab[i], tab[tab[i]]); vis[i] = vis[tab[i]] = true; } if (res.back().empty()) { res.pop_back(); } return true; } // bool inc_res() { // res.emplace_back(); // vis.reset(); // for (int i = 1; i <= n; i++) { // if (!vis[i]) { // int x = i; // while (!vis[x]) { // vis[x] = true; // if (!vis[tab[x]]) { // vis[tab[i]] = true; // res.back().push_back({x, tab[x]}); // swap(tab[x], tab[tab[x]]); // } // x = tab[x]; // } // } // } // // for (int i = 1; i <= n; i++) { // // if (tab[i] != i && !vis[i] && !vis[tab[i]]) { // // vis[i] = vis[tab[i]] = true; // // res.back().push_back({i, tab[i]}); // // swap(tab[i], tab[tab[i]]); // // } // // } // // for (int i = 1; i <= n; i++) { // // cout << tab[i] << " "; // // } // // cout << endl; // return !res.back().empty(); // } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) { cin >> tab[i]; } rescale(); // while (inc_res()) {} if (!make_inv()) { check(); make_inv(); } // cout << "witam "; // for (int i = 1; i <= n; i++) { // cout << tab[i] << " "; // } // cout << endl; // cout << "siema " << endl; cout << res.size() << "\n"; for (auto &vec : res) { if (vec.empty()) { break; } cout << 2 * vec.size() << "\n"; for (int i = 0; i < (int) vec.size(); i++) { cout << vec[i].first << " "; } for (int i = (int) vec.size() - 1; i >= 0; i--) { cout << vec[i].second << " "; } cout << "\n"; } } |