Zadanie

Keď George R. R. Martin1 začal písať svoju ságu A Song of Ice and Fire2, túto otázku si kládol veľmi často. Veľmi rýchlo však dospel k presvedčeniu, že aj tak všetci musia zomrieť3 a jeho knihy sa stali krvavým festivalom. Ako skúsený autor však vie, že je dôležité, v akom poradí jednotlivé postavy zomrú.

Má Bran zomrieť skôr ako Arya? A čo s Theonom, poprípade Petyrom Baelishom? Prežije Daenerys svojich drakov, alebo ju Drogon spáli svojim plameňom a potom zomrie v boji proti Jaimimu Lannisterovi? Všetky tieto otázky si musel George položiť a rozmýšľať, ktorá odpoveď je najlepšia. Postupne sa dopracoval k jednej možnej permutácii úmrtí, ktorá sa mu zdala ako veľmi dobrá.

Stále si však nebol istý (predsa len, všetkých možných permutácií je faktoriál veľa) a preto skúšal túto permutáciu zmeniť. Postupne vyskúšal všetky jej cyklické rotácie a porovnával ich medzi sebou. K najlepšiemu zisteniu však prišiel, keď lexikograficky zoradil všetky tieto cyklické rotácie jednu pod druhú a pozrel sa na čísla v poslednom stĺpci. Zdalo sa mu, že toto poradie úmrtí bude najlepšie možné.

Skôr ako si ho však zapísal, do izby vnikol prievan a odfúkol mu všetky papieriky s permutáciami. Zúfalý George si ale pamätá niekoľko prvých čísel jeho vysnívanej permutácie a to, že táto permutácia bola lexikograficky najmenšia možná s takýmto začiatkom. Pomôžte mu zistiť, ako vyzerá jeho zvolená permutácia, lebo zabije vaše obľúbené postavy ako prvé4.

Úloha

Najskôr si opäť zopakujme ako vznikla Georgova žiadaná permutácia. Na začiatku má permutáciu \(P\) zloženú z \(n\) prvkov – čísel od \(1\) po \(n\). Postupne si zoberie všetky cyklické rotácie tejto permutácie. Cyklickú rotáciu permutácie dostanete tak, že odstránite niekoľko prvých členov \(P\) a v takom istom poradí ich pridáte na koniec zvyšku tejto permutácie. Dostaneme teda \(n\) cyklických permutácií, lebo aj pôvodná permutácia patrí medzi jej cyklické permutácie.

Tieto permutácie teraz lexikograficky usporiadame a v tomto poradí zoradíme pod seba. Permutácia je lexikograficky menšia ako iná permutácia, ak má na prvej pozícii zľava, kde sa tieto permutácie líšia, menšie číslo. Dostaneme tabuľku \(n\times n\). Teraz si zoberme posledný stĺpec tejto tabuľky a dostaneme Georgovu vysnívanú permutáciu. Sami si rozmyslite, že táto postupnosť je naozaj permutácia.

Ukážme si tento postup na príklade. Majme permutácia \(P = (2, 4, 5, 1, 3)\).

cyklické rotácie       lexikograficky zoradené

2 4 5 1 3              1 3 2 4 5
4 5 1 3 2              2 4 5 1 3
5 1 3 2 4     ---->    3 2 4 5 1
1 3 2 4 5              4 5 1 3 2
3 2 4 5 1              5 1 3 2 4

Výsledná permutácia je \(R = (5, 3, 1, 2, 4)\).

A teraz prichádza vaša úloha. Poznáte niekoľko začiatočných prvkov permutácie \(R\), ktorá vznikla z nejakej permutácie \(P\) vyššie spomínaným postupom. Naviac viete, že \(R\) je lexikograficky najmenšia permutácia, ktorá mohla vzniknúť takýmto spôsobom a má daný začiatok. Zistite, ako vyzerá permutácia \(R\).

Formát vstupu

V prvom riadku je číslo \(n\) udávajúce počet prvkov hľadanej permutácie. V druhom riadku je číslo \(m\) – počet začiatočných prvkov permutácie \(R\), ktoré poznáte.

Tretí riadok obsahuje \(m\) čísel, ktoré určujú prvých \(m\) prvkov permutácie \(R\).

Formát výstupu

Vypíšte \(n\) čísel, každé na samostatný riadok. Tieto čísla majú tvoriť permutáciu \(R\), ktorá je lexikograficky najmenšia možná vzhľadom na podmienky vzniku a začiatočné prvky. V prípade, že takáto permutácia neexistuje, vypíšte reťazec Chybny vstup.

Hodnotenie

Vo všetkých vstupoch bude platiť, že \(n\leq 10^5\) a \(m \leq \min(n,10^5)\). Naviac môžete predpokladať, že v prvých dvoch testovacích sadách platí \(n\leq 10\) a v ďalších dvoch sadách platí, že \(n \leq 100\) a \(m \leq 50\).

Príklady

Input:

5
2
2 4

Output:

2
4
1
5
3

Input:

5
1
1

Output:

Chybny vstup

Input:

10
3
3 8 6

Output:

3
8
6
1
2
5
4
9
10
7

  1. Toto je len umelecké meno nášho obľúbeného Georga, vševedca, všeumelca a dobrodruha.

  2. Z ktorej k dnešnému dátumu vyšlo už 5 kníh a bol k nej natočený úspešný seriál Game of Thrones.

  3. Valar morghulis.

  4. Samozrejme, zomrú aj tak, ale môžete im zabezpečiť trošku dlhší život, poprípade menej drastickú smrť.

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 sebou1.

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 cesty2). 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é.

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.