Fişierul intrare/ieşire:xortransform.in, xortransform.outSursăLot Seniori Tulcea 2018, baraj 2
AutorBogdan Ciobanu, Bogdan IordacheAdăugată detamionvTamio Vesa Nakajima tamionv
Timp execuţie pe test2.5 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Xortransform

Se dă o matrice de numere naturale cu N linii și M coloane. Prin intermediul unei transformări putem obține o altă matrice de N linii și M coloane astfel: fiecare element de coordonate (i, j) cu 0 ≤ i < N, 0 ≤ j < M, din matricea nou obținută va fi egal cu suma xor a valorilor de la următoarele patru poziții (i, j), (i+1, j), (i, j+1), (i+1, j+1) din matricea inițială (dacă vreuna din pozițiile respective este în afara matricei, valoarea de la acea poziție se va considera 0).
Să se răspundă la Q întrebări de forma: care este valoarea de pe prima linie și prima coloană, dacă aplicăm K transformări asupra matricei inițiale.

Date de intrare

Pe primul rând al fişierului de intrare xortransform.in se vor găsi N, M şi Q
Pe următoarele N rânduri se vor găsi elementele matricii, câte M pe fiecare rând.
Pe următoarele Q rânduri se vor găsi valorile K ce ne intereseaza, codificate astfel: dacă valoarea citită este X, şi răspunsul la interogarea precedentă este Y (Y = 0 daca este vorba de prima interogare), atunci valoarea lui K în această interogare este X xor Y.

Date de ieşire

Fişierul de ieşire xortransform.out va conţine răspunsurile celor Q interogări, câte unul pe un rând.

Restricţii și precizări

  • 1 ≤ N*M ≤ 2 500 000
  • 1 ≤ elementele matricii ≤ 230
  • 1 ≤ K ≤ 1 000 000 000
  • Q ≤ 1 000 000

Exemplu

xortransform.inxortransform.out
4 5 3
9 8 1 3 6
1 2 5 2 5
3 4 3 7 7
7 8 3 5 1
3
31
108
13
8
15

Explicaţii

Valorile lui K pentru cele 3 interogări sunt, în ordine: 3, 18, 100.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?