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
#include <algorithm>
#include <deque>
#include <iostream>
#include <limits>
#include <utility>
#include <vector>

template <typename Collection>
void printCollection(const Collection& collection)
{
    for (int i = 0; i < collection.size(); i++) {
        std::cout << collection[i];
        if (i < collection.size() - 1) {
            std::cout << " ";
        }
    }
    std::cout << "\n";
}

// vector of size <1; 300'000>
// values in range <1; 300'000>
std::vector<int> getInput()
{
    int n;
    std::cin >> n;
    std::vector<int> v(n);
    for (int i = 0; i < n; i++) {
        std::cin >> v[i];
    }
    return v;

}

struct DataPack {
    int final_id{0};
    bool is_set_correctly{false};
};

class Data
{
   public:
    Data(const std::vector<int>& heights)
    {
        const auto [min_it, max_it] =
            std::minmax_element(heights.cbegin(), heights.cend());
        offset_ = *min_it;
        std::vector<int> tmp((*max_it - *min_it) + 1);
        data_.resize((*max_it - *min_it) + 1);

        for (auto height : heights) {
            tmp[height - offset_]++;
        }

        for (int i = 0, j = 1; i < data_.size(); i++) {
            if (tmp[i]) {
                data_[i].final_id = j;
                j++;
            }
        }
    }

    DataPack& operator[](const int height) { return data_[height - offset_]; }

    const DataPack& operator[](const int height) const { return data_[height - offset_]; }

   private:
    std::vector<DataPack> data_;
    int offset_{};
};

std::pair<int, std::deque<int>> round(std::vector<int>& heights, Data& data)
{
    std::deque<int> swaps{};
    int set_correctly{};
    std::vector<bool> was_swapped_this_round(heights.size(), false);
    for (int i = 0; i < heights.size(); i++) {
        auto& pack = data[heights[i]];
        if (not pack.is_set_correctly and not was_swapped_this_round[i] and
            pack.final_id == i + 1) {
            pack.is_set_correctly = true;
            set_correctly++;
        }
        if (pack.is_set_correctly or was_swapped_this_round[i] or
            was_swapped_this_round[pack.final_id - 1]) {
            continue;
        }
        // register swap
        swaps.push_front(i + 1);
        swaps.push_back(pack.final_id);

        pack.is_set_correctly = true;
        set_correctly++;

        // while doing swap verify if the other guy is set correctly too!
        auto& other_pack = data[heights[pack.final_id - 1]];
        if (other_pack.final_id - 1 == i) {
            other_pack.is_set_correctly = true;
            set_correctly++;
        }

        was_swapped_this_round[i] = true;
        was_swapped_this_round[pack.final_id - 1] = true;
    }
    for (int i = swaps.size() / 2 - 1; i >= 0; i--) {
        std::swap(heights[swaps[i] - 1], heights[swaps[swaps.size() - 1 - i] - 1]);
    }


    return {set_correctly, swaps};
}

int main()
{
    auto heights = getInput();
    auto data = Data(heights);

    int set_correctly = 0;
    std::vector<std::deque<int>> rounds{};
    while (set_correctly < heights.size() - 1) {
        auto [set, swaps] = round(heights, data);
        set_correctly += set;
        if (!swaps.empty()) {
            rounds.push_back(std::move(swaps));
        }
    }

    // output
    std::cout << rounds.size() << "\n";
    for (const auto& round : rounds) {
        std::cout << round.size() << "\n";
        printCollection(round);
    }
}