kmalloc

“Yellow sun, its evil twin,
In the black, the winds deliver him”

Umanitatea se află în pragul colapsului nuclear. Dr. Merkwürdigliebe proiectează un sistem de operare pentru ghidarea rachetelor. Supravieţuirea umanităţii depinde de algoritmul de alocare a memoriei, implementat de funcţia kmalloc.

Această funcţie primeşte un singur parametru size, număr natural, identifică o zonă continuă liberă de memorie de mărime $2^{size}$ şi returnează adresa de început a acesteia. După acest moment, zona respectivă de memorie devine ocupată.

Sistemul de operare are la dispoziţie $N$ octeţi numerotaţi de la 0 la N - 1. Se dau P intervale continue de memorie, care sunt rezervate deja şi nu pot fi folosite pentru alocare.

Programul pe care îl veţi scrie pentru a salva umanitatea va furniza o implementare a funcţiei kmalloc şi nu va citi şi nu va scrie din/în niciun fişier. În schimb, programul vostru va avea de implementat următoarele funcții:

void init(long long N, int P, std::vector<std::pair<long long, long long>> intervals);
long long kmalloc(int size);

Funcția init va fi apelată doar o dată la începutul fiecărui test și va furniza N - numărul de octeți disponibili, P - intervalele deja rezervate și un vector ce conține două numere întregi între 0 și N – 1, reprezentând adresa de început şi cea de sfârşit a intervalelor rezervate. Aceste intervale nu se vor suprapune şi vor fi date în ordinea crescătoare a adreselor ocupate.
Funcția kmalloc va fi apelată de mai multe ori în cadrul unui test și va trebui să returneze adresa de memorie de început a zonei alocate de mărime $2^{size}$.

Nu trebuie să implementația funcția main, dar puteți declara variabile/funcții suplimentare.

Restricţii şi precizări

• $1 ≤ N ≤ 2^{62}$
• Funcția kmalloc va fi apelată de maxim 500 000 ori per test
• 0 ≤ P ≤ 100 000
• Programul comisiei se va adapta la strategia aleasă de concurent.
• Se garantează că toate cererile de alocare de memorie pot fi satisfăcute de către un algoritm potrivit.

Exemplu

Este apelată funcția init(13, 2, {{5,5},{6,6}}) de către comisie.
Sunt 13 octeţi disponibili numerotaţi de la 0 la 12 și 2 intervale rezervate. Octetul 5 este rezervat, octetul 6 este rezervat.
Este apelată funcția kmalloc(2) ce va returna 0.
Se doreşte alocarea unei zone de 4 octeţi, se alocă octeţii 0, 1, 2, 3.
Este apelată funcția kmalloc(0) ce va returna 4.
Se doreşte alocarea unei zone de 1 octeţi, se alocă octetul 4.
Este apelată funcția kmalloc(1) ce va returna 7.
Se doreşte alocarea unei zone de 2 octeţi, se alocă octeţii 7, 8.
Este apelată funcția kmalloc(2) ce va returna 9.
Se doreşte alocarea unei zone de 4 octeţi, se alocă octeţii 9, 10, 11, 12.