Fişierul intrare/ieşire:parcare2.in, parcare2.outSursăOJI 2023, clasele 11-12
AutorBogdan SitaruAdăugată deIvanAndreiIvan Andrei •IvanAndrei
Timp execuţie pe test0.15 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Parcare2

În cel mai recent eveniment al companiei Tesla, Paul Musk a anunţat un nou produs inovativ: parcarea autonomată. Fiind cunoscut pentru lansările produselor incomplete, nici parcarea nu este completă, fiind nevoie de o automatizare pentru a atribui câte un loc maşinilor care vor să folosească parcarea.

Parcarea este formată din N locuri, numerotate de la 1 la N şi este deschisă timp de T secunde, începând cu secunda 1. Pe parcursul zilei, sosesc M maşini care vor să folosească parcarea, pentru fiecare dintre acestea ştiindu-se timpul de sosire si şi timpul de plecare pi. Maşinile vin în ordinea timpului de sosire si şi ocupă locul de parcare în intervalul de timp [si, pi]. Pentru fiecare dintre acestea, trebuie să afişaţi un loc liber de parcare (dacă sunt mai multe, se poate afişa oricare) în care aceasta se poate aşeza sau −1 dacă parcarea este plină în momentul venirii maşinii. Dacă o maşină nu are loc în parcare la timpul de sosire, aceasta nu va mai intra în parcare la niciun timp viitor.

La final, Paul este interesat de maşinile care mai sunt rămase în parcare la închiderea parcării, de aceea, vă cere să afişaţi configuraţia parcării la timpul T.

Date de intrare

Pe prima linie se găsesc trei numere întregi N, M şi T , reprezentând numârul de locuri din parcare, numărul de maşini care vin să folosească parcarea, respectiv numărul de secunde pentru care este deschisă parcarea.

Următoarele M linii conţin fiecare câte două numere întregi si, pi, reprezentând venirea unei maşini la secunda si care va pleca la secunda pi.

Maşinile apar în fişierul de intrare în ordine crescătoare după timpul de sosire si.

Date de ieşire

Se vor afişa M + 1 linii în total, primele M linii conţinând fiecare câte un număr întreg între 1 şi N reprezentând locul de parcare pe care îl va ocupa maşina, sau −1 dacă nu există niciun loc de parcare disponibil.

Restricţii

  • 1 ≤ N, M, T ≤ 200 000
  • 1 ≤ si ≤ T
  • 1 ≤ si < pi ≤ 200 000
  • Considerând următoarele 2M valori: s1, s2, ..., sM, p1, p2, ..., pM, acestea sunt distincte două câte două.
  • Dacă există mai multe soluţii, se poate afişa oricare dintre acestea.

Punctare

#PunctajRestricţii
124si + 1 = pi + 1, adică fiecare maşină stă exact o secundă.
226pi > sj, adică toate maşinile vin înainte ca vreo maşină să plece.
326N ≤ 1 000
424Fără restricţii suplimentare.

Exemplu

parcare2.inparcare2.outExplicaţii
2 4 6
1 3
2 10
4 6
5 8
2
1
2
-1
2 -1
Prima maşină soseşte în secunda 1 şi este parcată pe locul 2.
A doua maşină soseşte în secunda 2 şi este parcată pe locul 1.
În secunda 3 se eliberează locul 2.
Cea de-a treia maşină soseşte în secunda 4 şi ocupă locul 2.
Maşina sosită în secunda 5 nu găseşte loc liber.
În secunda 6 se eliberează locul 2.
După închiderea parcării, pe locul 1 va fi parcată maşina venită în secunda 2, locul al doilea fiind liber.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?