Fişierul intrare/ieşire:farfurii.in, farfurii.outSursăpreONI 2005 Runda 3
AutorMircea Bogdan PasoiAdăugată de
Timp execuţie pe test0.15 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Farfurii

In fiecare zi Zaharel este obligat de Eugenia sa spele farfuriile si tacamurile dupa fiecare masa. Dupa ce le spala el trebuie sa le aranjeze pe doua rafturi, farfuriile pe primul si tacamurile pe al doilea... dar nu oricum! El are N farfurii de marimi distincte, cuprinse intre 1 si N si K tacamuri identice. Pentru fiecare pereche de farfurii asezate in raft astfel incat farfuria de marime mai mare, dintre cele doua, apare inaintea farfuriei de marime mai mica, Zaharel pune un tacam pe randul al doilea.

Cerinta

Ajutati-l pe Zaharel sa aseze toate farfuriile pe primul raft astfel incat sa puna toate tacamurile pe al doilea raft. Dintre toate asezarile posibile determinati-o pe aceea minim lexicografica din punct de vedere al marimilor.

Date de intrare

Pe prima linie din fisierul de intrare farfurii.in se gasesc numerele naturale N si K.

Date de iesire

Pe prima linie din fisierul de iesire farfurii.out se vor gasi N numere distincte intre 1 si N reprezentand marimile farfuriilor, afisate in ordinea in care au asezate pe raft.

Restrictii

  • 1 ≤ N ≤ 100.000
  • 0 ≤ K ≤ N*(N-1)/2
  • Pentru cel putin 40% din teste N ≤ 2.000
  • O asezare (A1,A2...AN) este mai mica din punct de vedere lexicografic decat o alta asezare (B1,B2...BN) daca exista o pozitie p astfel incat Ap<Bp si A1=B1, A2=B2, ... Ap-1=Bp-1

Exemplu

farfurii.infarfurii.out
7 8
1 2 5 7 6 4 3

Explicatii

Pentru perechile de farfurii din asezare
(5 4) (5 3) (7 6) (7 4) (7 3) (6 4) (6 3) (4 3)
Zaharel pune cate un tacam pe randul al doilea. O alta asezare posibila este
1 2 6 5 7 4 3
dar aceasta este mai mare lexicografic.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content