Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2018-01-21 11:02:56.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:moft.in, moft.outSursăMarcel
AutorAlexandru PetrescuAdăugată dealexpetrescuAlexandru Petrescu •alexpetrescu
Timp execuţie pe test0.2 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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:

  • 1 test: t = 0, N ≤ 1.000, S ≤ 1.000, nu exista operatii de tipul 2
  • 1 test: t = 0, N ≤ 1.000, S ≤ 1.000
  • 1 test: t = 0, N ≤ 10.000, S ≤ 300
  • 1 test: t = 1, N ≤ 10.000, S ≤ 300, nu exista operatii de tipul 2
  • 1 test: t = 1, N ≤ 10.000, S ≤ 300
  • 1 test: t = 0, N ≤ 50.000, S ≤ 20, nu exista operatii de tipul 2
  • 2 teste: t = 0, N ≤ 50.000, S ≤ 20
  • 2 teste: t = 1, N ≤ 50.000, S ≤ 20, nu exista operatii de tipul 2
  • 3 teste: t = 1, N ≤ 50.000, S ≤ 20
  • 1 test: t = 0, N ≤ 200.000, S = 1, nu exista operatii de tipul 2
  • 1 test: t = 0, N ≤ 200.000, S = 1
  • 1 test: t = 1, N ≤ 200.000, S = 1, nu exista operatii de tipul 2
  • 4 teste: t = 1, N ≤ 200.000, S = 1

Exemplu

moft.inmoft.out
0 3
10
1 2 3 4 5 6 7 8 9 10
20
1 7
1 4
1 9
1 2
1 6
1 1
1 5
1 10
1 3
1 8
2 1
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
1
3
20
1 7
1 4
1 9
1 2
1 6
1 1
1 5
1 10
1 3
1 8
2 1
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
10
1 2 3 4 5 6 7 8 9 10
20
1 8
1 3
1 10
1 5
1 1
1 6
1 2
1 9
1 4
1 7
2 1
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
26034647
217
27243809

Explicaţie

7 P=7
4 7 P=28
4 7 9 P=252
2 4 7 9 P=504
2 4 6 7 9 P=3024
1 2 4 6 7 9 P=3024
1 2 4 5 6 7 9 P=15120
1 2 4 5 6 7 9 10 P=151200
1 2 3 4 5 6 7 9 10 P=453600
1 2 3 4 5 6 7 8 9 10 P=3628800
1 2 3 4 5 6 8 9 10 P=518400
1 2 3 5 6 8 9 10 P=129600
1 2 3 5 6 8 10 P=14400
1 3 5 6 8 10 P=7200
1 3 5 8 10 P=1200
3 5 8 10 P=1200
3 8 10 P=240
3 8 P=24
8 P=8
P=1

------------------

P=1
P=1
9 P=9
7 P=7
6 P=6
4 P=4
4 P=4
4 P=4
3 P=3
3 P=3
3 P=3
3 P=3
3 P=3
5 P=5
5 P=5
8 P=8
10 P=10
P=1
P=1
P=1

------------------

8 P=8
3 8 P=24
3 8 10 P=240
3 5 8 10 P=1200
1 3 5 8 10 P=1200
1 3 5 6 8 10 P=7200
1 2 3 5 6 8 10 P=14400
1 2 3 5 6 8 9 10 P=129600
1 2 3 4 5 6 8 9 10 P=518400
1 2 3 4 5 6 7 8 9 10 P=3628800
1 2 3 4 5 6 7 9 10 P=453600
1 2 4 5 6 7 9 10 P=151200
1 2 4 5 6 7 9 P=15120
1 2 4 6 7 9 P=3024
2 4 6 7 9 P=3024
2 4 7 9 P=504
4 7 9 P=252
4 7 P=28
7 P=7
P=1

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?