Proc2

proc2

== include(page="template/taskheader" task_id="proc2") ==

Avem un calculator cu $N$ procesoare. Există $M$ taskuri care trebuie executate, fiecare având un timp de început $S{~i~}$ şi o durată de procesare $D{~i~}$. Taskurile trebuie executate în ordine cronologică şi fiecare task trebuie executat pe procesorul cu indicele cel mai mic disponibil la momentul de timp $S{~i~}$.

Avem un calculator cu $N$ procesoare. Există $M$ taskuri care trebuie executate, fiecare având un timp de inceput $S{~i~}$ şi o durata de procesare $D{~i~}$. Taskurile trebuie executate în ordine cronologică şi fiecare task trebuie executat de procesorul cu indicele cel mai mic disponibil la momentul de timp $S{~i~}$.

h2. Cerinţă

h2. Cerintă

Trebuie calculat pentru fiecare task procesorul care îl va executa.
h2. Date de intrare

Fişierul de intrare $proc2.in$ conţine pe prima linie valorile $N$ şi $M$. Pe următoarele $M$ linii se vor găsi câte două numere $S{~i~}$, $D{~i~}$ separate prin spaţii, cu semnificaţia din enunţ.

Fişierul de intrare $proc2.in$ conţine pe prima linie valorile $N$ şi $M$. Pe următoarele $M$ linii se vor găsi cate două numere $S{~i~}$, $D{~i~}$ separate prin spaţii, cu semnificaţia din enunţ.

h2. Date de ieşire

În fişierul de ieşire $proc2.out$ trebuie afişate $M$ linii. Pe linia $i$ se va scrie indicele procesorului pe care se execută taskul $i$.

În fişierul de ieşire $proc2.out$ trebuie afişate $M$ linii, pe linia $i$ se va scrie indicele procesorului care se ocupă de taskul $i$.

h2. Restricţii
* $1 ≤ N ≤ 1.000.000$
* $1 ≤ M ≤ 100.000$

* Pentru orice $i$ între $1$ şi $M$, {$1 ≤ S{~i~} ≤ 2*10^9^$} şi {$1 ≤ S{~i~}+D{~i~} ≤ 2*10^9^$}
* Pentru orice $i$ între $1$ şi $M-1$, {$S{~i~} < S{~i+1~}$}
* Se garantează că fiecare task poate fi executat
* Procesorul care execută taskul $i$ este ocupat la momentele de timp $[S{~i~}, S{~i~} + D{~i~})$

* se garantează ca fiecare task poate fi executat
* toate valorile $S{~i~}$ sunt distincte
* procesorul care executa taskul $i$ este ocupat la momentele de timp $[S{~i~}, S{~i~} + D{~i~})$

h2. Exemplu
table(example). |_. proc2.in |_. proc2.out |
| 3 3

1 2

1 1

2 3
3 3
| 1

5445