#include <bits/stdc++.h> using namespace std; #define sim template < class c #define ris return * this #define dor > debug & operator << #define eni(x) sim > typename \ enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) { sim > struct rge { c b, e; }; sim > rge<c> range(c i, c j) { return rge<c>{i, j}; } sim > auto dud(c* x) -> decltype(cerr << *x, 0); sim > char dud(...); struct debug { #ifdef LOCAL ~debug() { cerr << endl; } eni(!=) cerr << boolalpha << i; ris; } eni(==) ris << range(begin(i), end(i)); } sim, class b dor(pair < b, c > d) { ris << "(" << d.first << ", " << d.second << ")"; } sim dor(rge<c> d) { *this << "["; for (auto it = d.b; it != d.e; ++it) *this << ", " + 2 * (it == d.b) << *it; ris << "]"; } #else sim dor(const c&) { ris; } #endif }; #define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] " // debug & operator << (debug & dd, P p) { dd << "(" << p.x << ", " << p.y << ")"; return dd; } int main() { int n; scanf("%d", &n); vector<int> h(n); for (int i = 0; i < n; ++i) { scanf("%d", &h[i]); } vector<int> p(n); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (h[j] < h[i]) { p[i]++; } } } debug() << imie(p); vector<vector<int>> answer; while (true) { vector<pair<int,int>> pairs; vector<bool> visited(n); for (int i = 0; i < n; ++i) { if (p[i] != i && !visited[i]) { vector<int> cycle; int j = i; do { j = p[j]; cycle.push_back(j); visited[j] = true; } while (i != j); int k = cycle.size(); for (int z = 0; z < k / 2; ++z) { pairs.emplace_back(cycle[z], cycle[k-1-z]); } } } if (pairs.empty()) { break; } for (pair<int,int> pp : pairs) { swap(p[pp.first], p[pp.second]); } vector<int> row; for (pair<int,int> pp : pairs) { row.push_back(pp.first); } reverse(pairs.begin(), pairs.end()); for (pair<int,int> pp : pairs) { row.push_back(pp.second); } answer.push_back(row); } printf("%d\n", (int) answer.size()); for (vector<int> v : answer) { printf("%d\n", (int) v.size()); for (int x : v) { printf("%d ", x + 1); } puts(""); } }
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 | #include <bits/stdc++.h> using namespace std; #define sim template < class c #define ris return * this #define dor > debug & operator << #define eni(x) sim > typename \ enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) { sim > struct rge { c b, e; }; sim > rge<c> range(c i, c j) { return rge<c>{i, j}; } sim > auto dud(c* x) -> decltype(cerr << *x, 0); sim > char dud(...); struct debug { #ifdef LOCAL ~debug() { cerr << endl; } eni(!=) cerr << boolalpha << i; ris; } eni(==) ris << range(begin(i), end(i)); } sim, class b dor(pair < b, c > d) { ris << "(" << d.first << ", " << d.second << ")"; } sim dor(rge<c> d) { *this << "["; for (auto it = d.b; it != d.e; ++it) *this << ", " + 2 * (it == d.b) << *it; ris << "]"; } #else sim dor(const c&) { ris; } #endif }; #define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] " // debug & operator << (debug & dd, P p) { dd << "(" << p.x << ", " << p.y << ")"; return dd; } int main() { int n; scanf("%d", &n); vector<int> h(n); for (int i = 0; i < n; ++i) { scanf("%d", &h[i]); } vector<int> p(n); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (h[j] < h[i]) { p[i]++; } } } debug() << imie(p); vector<vector<int>> answer; while (true) { vector<pair<int,int>> pairs; vector<bool> visited(n); for (int i = 0; i < n; ++i) { if (p[i] != i && !visited[i]) { vector<int> cycle; int j = i; do { j = p[j]; cycle.push_back(j); visited[j] = true; } while (i != j); int k = cycle.size(); for (int z = 0; z < k / 2; ++z) { pairs.emplace_back(cycle[z], cycle[k-1-z]); } } } if (pairs.empty()) { break; } for (pair<int,int> pp : pairs) { swap(p[pp.first], p[pp.second]); } vector<int> row; for (pair<int,int> pp : pairs) { row.push_back(pp.first); } reverse(pairs.begin(), pairs.end()); for (pair<int,int> pp : pairs) { row.push_back(pp.second); } answer.push_back(row); } printf("%d\n", (int) answer.size()); for (vector<int> v : answer) { printf("%d\n", (int) v.size()); for (int x : v) { printf("%d ", x + 1); } puts(""); } } |