Začnime tým, že si zopakujeme zadanie úlohy, keďže je mierne komplikované. Na začiatku sme mali permutáciu $$n$$ čísel, ktorú si označíme $$P$$. Zobrali sme všetky cyklické rotácie tejto permutácie a lexikograficky sme ich usporiadali. Z každej permutácie sme postupne zobrali posledné číslo (v takom poradí ako boli usporiadané), čím sme dostali permutáciu $$R$$. Nanešťastie, zachovalo sa nám iba niekoľko začiatočných čísel permutácie $$R$$, ale vieme, že zo všetkých vhodných permutácii, bola $$R$$ lexikograficky najmenšia. No a úlohou je nájsť permutáciu $$R$$.

A tu sa nachádza chyták tejto úlohy. Aj keď budeme hľadať permutáciu $$R$$, oveľa dôležitejšia bude pre nás permutácia $$P$$, hlavne fakt, že je to permutácia. Ak sme spravili cyklické permutácie $$P$$ a lexikograficky ich zoradili, dostali sme tabuľku $$n\times n$$. Permutácia $$R$$ nám tvorí posledný stĺpec tejto tabuľky. Ale my poznáme aj prvý stĺpec. Musia to byť predsa čísla od $$1$$ po $$n$$ zoradené za sebou[^1].

A čo nám určuje prvý a posledný stĺpec tejto tabuľky? Hovorí to o vzájomnom vzťahu za sebou idúcich čísel v permutácii $$P$$. Ak máme v nejakom riadku na začiatku číslo $$x$$ a na konci číslo $$y$$, znamená to, že v permutácii $$P$$ sa číslo $$x$$ nachádza hneď za číslom $$y$$. Permutáciu $$P$$ teda môžeme zapísať ako graf, kde vrcholy predstavujú čísla od $$1$$ po $$n$$ a šípka z vrcholu $$x$$ do vrcholu $$y$$ bude znamenať, že číslo $$x$$ sa v permutácii $$P$$ nachádza hneď za číslom $$y$$ (pričom prvé číslo permutácie $$P$$ sa nachádza hneď za posledným číslom $$P$$). Takto dostaneme jeden cyklus dĺžky $$n$$.

Toto je jediná podmienka, ktorú sa budeme snažiť dodržať. Pri vytváraní $$R$$ budeme postupne zisťovať závislosti, ktoré platia v $$P$$ a hrany zodpovedajúce týmto závislostiam budeme pridávať do našeho grafu. Budeme sa pritom snažiť, aby sme na konci naozaj dostali jeden veľký cyklus. Hocičo iné by znamenalo, že naše $$R$$ nevzniklo z permutácie.

Pre jednoduchosť vzoráku budeme predpokladať, že sa nezachovalo žiadne z čísel $$R$$, čiže $$m=0$$. V opačnom prípade sa zmení akurát to, že niektoré závislosti budú určené vopred a môže sa nám stať, že dáta nebudú konzistentné a povedú k sporu, ktorý spôsobí, že riešenie nebude existovať. V ďalšej časti si však aj tak povieme, čo tento spor je a preto táto časť programu je takmer totožná tej druhej.

Uvedomme si, ako vyzerá náš graf, ktorý reprezentuje permutáciu $$P$$, ak sme ešte nepridali všetky závislosti. V tomto grafe môže z každého vrcholu vychádzať najviac jedna hrana a naviac tu nemôže byť žiaden cyklus. Cyklus totiž môže vzniknúť až na úplnom konci. Ľubovoľný menší cyklus by znamenal, že už nikdy sa nám neporadí spraviť jeden veľký cyklus dĺžky $$n$$. Tento graf teda musí byť tvorený niekoľkými cestami.

Naviac, vnútorné vrcholy týchto ciest nás už nezaujímajú, lebo vieme, ktorý vrchol je pred nimi aj za nimi a viac hrán do nich ísť nemôže. Jediné zaujímavé sú teda vrcholy na začiatku a konci cesty. Počas našeho algoritmu si teda musíme udržiavať tieto začiatky a konce. Jedna rozumná reprezentácia je nasledovná: pre každý koncový vrchol nejakej cesty si budem pamätať začiatok tejto cesty (toto budeme mať v poli $$K$$) a pre každý začiatočný vrchol si pamätám koniec tejto cesty (pole $$Z$$).

Predstavme si, že už sme určili (alebo boli určené) prvých $$i-1$$ čísiel permutácie $$R$$ a máme vytvorený graf obsahujúce príslušené zistené závislosti. Pozeráme sa preto na $$i$$-ty riadok našej $$n\times n$$ tabuľky. Na jej začiatku je číslo $$i$$ a chystáme sa určiť, aké najmenšie číslo $$x$$ môžeme dať na jej koniec. V našom grafe to vytvorí hranu z vrchola $$i$$ (ktorý je začiatok nejakej cesty) do vrchola $$x$$ (ktorý musí byť koniec nejakej cesty[^2]). Vieme teda, že číslo $$x$$ musí zodpovedať vrcholu na konci nejakej cesty a kedže $$R$$ sa snažíme spraviť lexikograficky najmenšie, vyberieme najmenšie možné $$x$$.

Toto má ale jeden prípad, keď to nemôžeme spraviť. A to práve vtedy, ak je $$x$$ na konci cesty, kde je $$i$$ na začiatku. Pridaním takejto závislosti by sme totiž vytvorili nechcený cyklus. V takom prípade ale môžeme zobrať druhé najmenšie $$x$$, keďže na konci cesty začínajúcej s $$i$$ je len jedno číslo. Toto je zároveň prípad, ktorý môže spôsobiť nekonzistenciu vstupných dát.

Posledné čo zostáva je, ako rýchlo nájsť najmenšie (poprípade druhé najmenšie) číslo z koncových vrcholov. Hneď by vás malo napadnúť, že môžeme použiť dátovú štruktúru halda, kde vieme skladovať tieto čísla a rýchlo vybrať najmenšie z nich (a na vybratie druhého najmenšieho proste vyberieme dve najmenšie čísla a to prvé vrátime).

Následne už len správne upravíme polia $$Z$$ a $$K$$. Začiatok tejto novej cesty bude vrchol $$Z[x]$$ a koniec bude $$K[i]$$. Správne úpravy budú teda $$K[Z[x]]=K[i]$$ a $$Z[K[i]]=Z[x]$$.

Zostáva nám už len odhadnúť pamäťovú a časovú zložitosť. Pamäte nám stačí $$O(n)$$, lebo si pamätáme len niekoľko lineárnych polí. Pri časovej musíme zarátať logaritmický faktor haldy, použijeme ju však lineárne veľa krát a preto bude časová zložitosť $$O(n\log n)$$.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

#define For(i,n) for(int i=0; i<(n); i++)

int main() {
    int n;
    scanf("%d",&n);
    vector<int> Z,K;
    For(i,n) Z.push_back(i);
    For(i,n) K.push_back(i);
    vector<int> V;
    bool spravne = true;
    int m;
    scanf("%d",&m);
    For(i,m) {
        int x;
        scanf("%d",&x);
        x--;
        V.push_back(x);
        if((K[i]==-1 || K[i]==x) && i!=n-1) {spravne=false; continue;}
        Z[K[i]]=Z[x]; K[Z[x]]=K[i];
        K[i]=Z[x]=-1;
    }
    priority_queue<int> Q;
    For(i,n) if(Z[i]!=-1) Q.push(-i);
    for(int i=m; i<n; i++) {
        if(Q.size()==0) continue;
        int x=-Q.top(); Q.pop();
        if(K[i]==x && Q.size()!=0) {
            int y=-Q.top(); Q.pop();
            Q.push(-x);
            x=y;
        }
        V.push_back(x);
        Z[K[i]]=Z[x]; K[Z[x]]=K[i];
        K[i]=Z[x]=-1;
    }
    if(!spravne) {printf("Chybny vstup\n"); return 0;}
    For(i,V.size()) printf("%d\n",V[i]+1);
}

1. Ak robíme cyklické rotácie nejakej permutácie, pre každé možné číslo od $$1$$ po $$n$$ nám vznikne permutácia s týmto začiatkom. No a lexikografické usporiadanie potom musí triediť podľa týchto rôznych začiatkov.↩

2. Rozmyslite si, prečo to platí, nie je to ťažké.↩