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, care va fi afisat in 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 contine pe prima linie numarul t, a carui utilitate a fost evidentiata mai sus, si numarul T de teste. Structura fiecarui test e urmatoarea: Pe prima linie se afla numarul S, pe a doua cele S numere Ki, pe a treia numarul N de operatii, iar pe urmatoarele N linii cate o pereche u H, unde u este fie 1, fie 2, in functie de tipul operatiei, iar H trebuie modificat dupa cum este explicat mai sus.
Date de ieşire
În fişierul de ieşire moft.out se afla, pentru fiecare din cele T teste, cate un numar, reprezentand raspunsul final care este calculat dupa cum ati citit.
Restricţii
- 1 ≤ H, Ki ≤ 1.000.000.000
- 1 ≤ T ≤ 3
- 1 ≤ N, S
Punctare
La evaluare vor fi folosite 20 de teste, fiecare valorand cate 5 puncte. Ele sunt organizate dupa cum urmeaza:
- 2 teste: t = 0, N ≤ 1.000, S ≤ 1.000
- 1 test: t = 0, N ≤ 10.000, S ≤ 1.000
- 2 teste: t = 1, N ≤ 10.000, S ≤ 1.000
- 2 teste: t = 0, N ≤ 1.000.000, S = 1
- 5 teste: t = 1, N ≤ 1.000.000, S = 1
- 3 teste: t = 0, N ≤ 200.000, S ≤ 50
- 5 teste: t = 1, N ≤ 200.000, S ≤ 50
Recomandare
Parsati intrarea folosind functia fread.
Exemplu
| moft.in | moft.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
