Fişierul intrare/ieşire:invinv.in, invinv.outSursăRomanian Collegiate Programming Contest 2019
AutorMihai CalanceaAdăugată deRCPC2019RCPC2019 RCPC2019
Timp execuţie pe test0.6 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultateN/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.ininvinv.out
3
1 0
4 1
4 6
1
1 3 2 4
4 3 2 1
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?