Fişierul intrare/ieşire: | invinv.in, invinv.out | Sursă | Romanian Collegiate Programming Contest 2019 |
Autor | Mihai Calancea | Adăugată de | |
Timp execuţie pe test | 0.3 sec | Limită de memorie | 16384 kbytes |
Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Invinv
Fie P o permutare de ordin N. Numim inversiune o pereche de indici (i, j) cu proprietatea că i < j şi P[i] > P[j].
În acestă problemă trebuie să afişaţi o permutare de ordin N cu exact K inversiuni.
Date de intrare
Fişierul de intrare invinv.in va conţine pe prima sa linie valoarea T, reprezentând numărul de teste din fişierul de intrare.
Următoarele T linii vor conţine câte o pereche de numere N şi K.
Date de ieşire
În fişierul de ieşire invinv.out se vor afla T linii. A i-a linie va conţine o permutare corespunzătoare pentru al i-lea test din fişierul de intrare.
Restricţii
- 1 ≤ N ≤ 50.000
- 0 ≤ K ≤ N * (N - 1) / 2
- Se acceptă orice permutare de ordin N cu K inversiuni.
- Se garantează că suma valorilor lui N în cadrul unui fişier de intrare este cel mult egală cu valoarea 600.000.
- Observaţi că nu există o limitare explicită a lui T.
Exemplu
invinv.in | invinv.out |
---|---|
3 1 0 4 1 4 6 | 1 1 3 2 4 4 3 2 1 |