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
#include <bits/stdc++.h>

using namespace std;

#define f   first
#define s   second

int students_nb;
vector<int> students_heights;
vector<vector<int>> answers;

int Solve();
bool makeRound();

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cin >> students_nb;
    students_heights = vector<int>(students_nb);
    for (int i = 0; i < students_nb; i++) {
        cin >> students_heights[i];
    }
    int nb_rounds = Solve();
    cout << nb_rounds << endl;
    for (int i = 0; i < nb_rounds; i++) {
        cout << answers[i].size() << endl;
        for (int j = 0; j < answers[i].size(); j++) {
            cout << answers[i][j] << " ";
        }
        cout << endl;
    }
    // for (int i = 0; i < students_nb; i++) {
    //     cout << students_heights[i].f << " ";
    // }
    // cout << endl;
    return 0;
}

int Solve() {
    if (makeRound()) {
        if (makeRound()) {
            return 2;
        }
        return 1;
    }
    return 0;
    
}

bool makeRound() {
    vector<pair<int, int>> sorted_heights(students_nb);
    for (int i = 0; i < students_nb; i++) {
        sorted_heights[i] = {students_heights[i], i};
    }
    sort(sorted_heights.begin(), sorted_heights.end());
    vector<bool> visited(students_nb);
    queue<int> left_swap;
    stack<int> right_swap;
    for (int i = 0; i < students_heights.size(); i++) {
        if (students_heights[i] != sorted_heights[i].f) {
            visited[i] = true;
            list<int> items_to_swap;
            items_to_swap.push_front(i);
            int next_one = sorted_heights[i].s;
            while (!visited[next_one]) {
                visited[next_one] = true;
                items_to_swap.push_front(next_one);
                next_one = sorted_heights[next_one].s;
            }
            while (items_to_swap.size() > 1) {
                int l = items_to_swap.back();
                int r = items_to_swap.front();
                items_to_swap.pop_back();
                items_to_swap.pop_front();
                swap(students_heights[l], students_heights[r]);
                left_swap.push(l + 1);
                right_swap.push(r + 1);
            }
        }
    }
    if (not left_swap.empty()) {
        int swap_nb = left_swap.size();
        vector<int> swap_positions(swap_nb * 2);
        for (int i = 0; i < swap_nb; i++) {
            int l = left_swap.front();
            int r = right_swap.top();
            left_swap.pop();
            right_swap.pop();
            swap_positions[i] = l;
            swap_positions[i + swap_nb] = r;
        }
        answers.push_back(swap_positions);
        return true;
    }
    return false;
}