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
#include<bits/stdc++.h>
using namespace std;
pair<pair<int,int>,pair<int,int> > tablica[3030]; /// pierwsze to tablica wartoœci (posortowana po tym), kolejne to pozycja w oryginalnym kolejne to pozycja w posortowanym a czwarte to kiedy by³o modyfikowane (czas)
/// < <value,orig_poz>,<sort_poz,last_modified> >
/// pomys³: najpierw wczytujemy ci¹g, zapisujemy kolejnoœæ, nastêpnie sortujemy rosn¹co, zapisujemy docelow¹ pozycjê ka¿dego elementu, potem wracamy kolejnoœæ do poprzedniego stanu.
/// nastêpnie sprawdzamy ile elementów jest na docelowej pozycji i dopóki wszystkie nie s¹, puszczamy while'a. Wtedy przechodzimy po tablicy
vector <pair<int,int> > odpowiedz[5005];
bool comp(pair<pair<int,int>,pair<int,int>> a,pair<pair<int,int>,pair<int,int>> b)
{
    return a.first.second<b.first.second;
}
bool comp2(pair<pair<int,int>,pair<int,int>> a,pair<pair<int,int>,pair<int,int>> b)
{
    return a.first.first<b.first.first;
}
int main()
{
    int a,on_poz,time=0,pos=0,b;
    cin >> a;
    on_poz=a; /// liczba liczb które nie są na docelowej pozycji
    for(int i=0;i<a;i++)
    {
        cin >> b;
        tablica[i]=make_pair(make_pair(b,i),make_pair(0,0));
    }
    sort(tablica,tablica+a,comp2); /// sortowanie tablicy rosnąco (docelowy wynik)
    for(int i=0;i<a;i++)
    {
        tablica[i].second.first=i; /// zapisywanie dla każdej liczby gdzie powinna ona być
        if(tablica[i].first.second==i)
            on_poz--; /// jeśli dla ciągu dobrego i dla ciągu startowego są na tej samej pozycji, to zapisujemy, że jedna liczba więcej jest na pozycji.
            /// w późniejszym etapie kodu tej liczby nie zapisujemy do countera z powodu ifa
    }
    sort(tablica,tablica+a,comp); /// sortowanie tablicy w pierwotnej kolejności, lecz z zapisanymi wartościami gdzie one powinny być
    ///cout << on_poz << "\n";
    while(on_poz>0) /// dopóki wszystkie wartości nie będą na pozycjach
    {
        for(int i=0;i<a;i++)
        {
            pos=i; /// przechodzimy się po całej tablicy i sprawdzamy czy element był odwiedzony oraz czy jest na pozycji własnej
            while(tablica[tablica[pos].second.first].second.second!=time+1 && tablica[pos].second.second!=time+1) /// dopóki dana liczba i ta z którą ma się zamienić nie były już zamieniane w tej turze
            {
                if(tablica[pos].second.first!=pos) /// jeśli nie znajduje się na docelowym wierzchołku, to wierzchołek będący na celu tym bardziej nie jest na celu.
                {
                    tablica[pos].second.second=time+1; /// ustawia obecny na odwiedzony
                    odpowiedz[time].push_back(make_pair(pos,tablica[pos].second.first)); /// do odpowiedzi dodaje parę tego wierzchołka i kolejnego
                    swap(tablica[pos],tablica[tablica[pos].second.first]); /// zamiana wierzchołków
                    tablica[pos].second.second=time+1; /// nowy wierzchołek też jest już odwiedzony
                    on_poz--; /// stary wierzchołek jest na pozycji
                    if(tablica[pos].second.first==pos)
                        on_poz--; /// jeśli nowy też jest na pozycji, to dodajemy kolejny jako na pozycji
                    pos=tablica[pos].second.first; /// odwiedzany wierzchołek to kolejny na cyklu
                }
                else
                    tablica[pos].second.second=time+1; /// jeśli ten wierzchołek jednak jest już na pozycji to pomijamy go i idziemy dalej forem (nie jestem pewien może break nie działał
            }
        }
        time++;
        ///cout << on_poz << "\n";
    }
    cout << time;
    if(time!=0)
    {
        for(int i=0;i<time;i++)
        {
            cout << "\n" << odpowiedz[i].size()*2 << "\n";
            for(int j=0;j<odpowiedz[i].size();j++)
            {
                cout << odpowiedz[i][j].first+1 << " ";
            }
            for(int j=odpowiedz[i].size()-1;j>=0;j--)
            {
                cout << odpowiedz[i][j].second+1 << " ";
            }
        }
    }
}