Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | moft.in, moft.out | Sursă | Marcel |
| Autor | Alexandru Petrescu | Adăugată de |  Alexandru Petrescu •alexpetrescu |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate |   4/5 |
Vezi solutiile trimise | Statistici
Moft
Marcel se afla acum intr-un univers foarte abstract. Numerele capata sentiment, iar capriciile lor devin supradimensionate. Asa se face ca sunt S numere mofturoase, fie ele Ki, si un multiset de numere initial vid. Amintim faptul ca intr-un multiset un numar poate aparea de mai multe ori. Asupra multisetului se fac N operatii:
- 1 x : este inserat numarul x in multiset. Acestuia i se asociaza un numar id egal cu cel mai mic numar natural nenul care nu a mai fost asociat altui numar inainte.
- 2 id : este sters din multiset numarul caruia i-a fost asociat numarul id. Se garanteaza ca acesta se afla in multiset.
Dupa fiecare din aceste N operatii, fiecare din cele S numere mofturoase se intreaba care ar fi numarul de pe pozitia Ki daca am aranja crescator numerele din multiset.
Detalii tehnice
Pentru a nu supraincarca fisierul de iesire cu toate mofturile numerelor, si pentru a ne asigura ca numai solutiile cele mai deosebite vor fi punctate corespunzator, dupa fiecare operatie se calculeaza numarul P ca fiind produsul raspunsurilor la cele S intrebari, modulo 1.000.000.007. Daca intrebarea este invalida, adica Ki > $ numarul elementelor din multiset, $P nu se modifica (se simuleaza inmultirea cu elementul neutru, si anume 1). In functie de el, se va stabili si numarul care urmeaza sa fie inserat sau sters, dupa cum urmeaza: Daca numarul din input este H, valoarea utilizata este data de H xor (P * t), iar t este o valoare cunoscuta, egala fie cu 0, fie cu 1. Pentru prima operatie se va considera ca P = 1. Valoarea lui P nu trebuie afisata, ci folosita pentru calcularea raspunsului final, singurul numar din output, care va fi egal cu (P1 * 1) xor (P2 * 2) xor ... xor (PN * N), unde cu Pi am notat valoarea lui P dupa primele i operatii. A se observa ca valoarea care trebuie afisata nu este calculata modulo 1.000.000.007!
Date de intrare
Fişierul de intrare moft.in ...
Date de ieşire
În fişierul de ieşire moft.out ...
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| moft.in | moft.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
