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 using namespace std; using LL=long long; #define FOR(i,l,r) for(int i=(l);i<=(r);++i) #define REP(i,n) FOR(i,0,(n)-1) #define ssize(x) int(x.size()) templateauto&operator<<(ostream&o,pairp){return o<<'('<auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<sync_with_stdio(0); int n; cin >> n; debug(n); vector a(n); REP(i, n) cin >> a[i]; debug(a); auto sorted = a; sort(sorted.begin(), sorted.end()); REP(i, n) a[i] = int(lower_bound(sorted.begin(), sorted.end(), a[i]) - sorted.begin()); debug(a); vector> ans; while (not is_sorted(a.begin(), a.end())) { vector vis(n); vector left, right; auto add_swap = [&](int i, int j) { left.emplace_back(i); right.emplace_back(j); }; function)> solve_cycle = [&](vector v) { debug("solve_cycle", v); if (v.empty() or v.back() == -1) return; int x = 0; while (v[x] == -1) ++x; assert(x == 1); int other = ssize(v) - 1; debug(x, other); if (x == other) return; add_swap(v[x], v[other]); vector rec_vec(v.begin() + 1, v.end() - 1); if (ssize(rec_vec)) { rec_vec[0] = -1; solve_cycle(rec_vec); } }; REP(i, n) { if (vis[i] or a[i] == i) continue; int x = i; vector ids; while (not vis[x]) { ids.emplace_back(x); vis[x] = true; x = a[x]; } if (ssize(ids) < 2) continue; add_swap(ids[0], ids[1]); ids.erase(ids.begin()); ids[0] = -1; solve_cycle(ids); } left.insert(left.end(), right.rbegin(), right.rend()); debug(left); ans.emplace_back(left); const int s = ssize(left); REP(i, s / 2) swap(a[left[i]], a[left[s - 1 - i]]); debug(a); } cout << ssize(ans) << '\n'; #ifndef LOCAL for (auto v : ans) { cout << ssize(v) << '\n'; for (auto e : v) { cout << e + 1 << ' '; } cout << '\n'; } #endif }