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
#include <algorithm>
#include <cstdio>
#include <vector>

const int MAX_PEOPLE = 8192;

int people;
int height[MAX_PEOPLE];
int seq[MAX_PEOPLE];
int cycle[MAX_PEOPLE];
bool order;
std::vector<std::vector<int>> steps;

void swapper(const int cyc[], size_t start, size_t end)
{
    if(end <= start)
        return;

    if(end - start == 1)
    {
        steps.back().push_back(cyc[start] + 1);
        steps.back().push_back(cyc[end] + 1);
        std::swap(height[cyc[start]], height[cyc[end]]);
        return;
    }

    steps.back().push_back(cyc[start] + 1);
    steps.back().push_back(cyc[(start + end) / 2] + 1);
    std::swap(height[cyc[start]], height[cyc[(start + end) / 2]]);

    swapper(cyc, start + 1, (start + end) / 2 - 1);

    if(end - start > 2)
    {
        steps.back().push_back(cyc[(start + end) / 2 + 1] + 1);
        steps.back().push_back(cyc[end] + 1);
        std::swap(height[cyc[end]], height[cyc[(start + end) / 2 + 1]]);
        swapper(cyc, (start + end) / 2 + 2, end - 1);
    }
}

int main(void)
{
    scanf("%d", &people);
    for(int p = 0; p < people; ++p)
    {
        scanf("%d", &height[p]);
        seq[p] = p;
    }

    // Number the people by height
    std::sort(seq, seq + people, [](int a, int b)
        { return height[a] < height[b]; });

    for(int p = 0; p < people; ++p)
        height[seq[p]] = p;

    do
    {
        order = true;
        bool seen[MAX_PEOPLE] = {};
        for(int p = 0; p < people; ++p)
        {
            if(seen[p])
                continue;

            if(height[p] == p)
                continue;

            if(order)
                steps.push_back({});

            order = false;
            int c = 0;
            cycle[c++] = p;
            seen[p] = true;
            for(int s = height[p]; s != p; s = height[s])
            {
                seen[s] = true;
                cycle[c++] = s;
            }

            swapper(cycle, 0, c - 1);
        }
    } while(!order);

    printf("%lu\n", steps.size());
    for(const auto &step: steps)
    {
        printf("%lu\n", step.size());
        for(size_t s = 0; s < step.size(); s += 2)
            printf("%d ", step[s]);

        for(ssize_t s = step.size() - 1; s > 0; s -= 2)
            printf("%d ", step[s]);

        puts("");
    }

    return 0;
}