Unirea pentru Performanta XI-XII 2024 | skill issue

Ștefan și Tudor se plictisesc așa că se joacă un joc inovativ. Cei doi au în față câte o tablă virtuală care poate fi reprezentată ca o matrice de $N \cdot M$, unde $N$ și $M$ sunt numere naturale nenule.

Ștefan are inițial tabla $A$, iar Tudor tabla $B$.

Regulile jocului:

La început, toate căsuțele din interiorul tablelor vor fi umplute cu numere aleatorii. Jocul se desfășoară în $Q$ runde, fiecare rundă poate fi de tip $1$ sau de tip $2$.

Dacă runda este de tip $1$ atunci:

• se dă o căsuță $(x_A, y_A)$ a tablei $A$ în care numărul devine $val_1$.
• se dă o căsuță $(x_B, y_B)$ a tablei $B$ în care numărul devine $val_2$.

Dacă runda este de tip $2$ atunci:

• se dau colțurile $x_1, y_1, x_2, y_2$ unei submatrici ale tablei $A$ și se determină puterea $P_A$ a submatricii.
• se dau colțurile $x_3, y_3, x_4, y_4$ unei submatrici ale tablei $B$ și se determină puterea $P_B$ a submatricii.
• dacă $P_A > P_B$, atunci cel care este desemnat tablei $A$ primește un punct, iar dacă $P_A < P_B$, cel care este desemnat tablei $B$ primește un punct. În caz de egalitate nimeni nu primește puncte.
• Puterea $P$ a unei submatrici se definește ca restul sumei efectuării operației "xor" pe biți între elementele tuturor submulțimilor din submatrice la $10^9 + 7$.

Exemplu: Dacă elementele submatricii sunt $1$, $2$, $3 \rightarrow P = (1 + 2 + 3 + (1 \oplus 2) + (1 \oplus 3) + (2 \oplus 3) + (1 \oplus 2 \oplus 3))$ % $( 10^9 + 7) = 12$, unde $\oplus$ reprezintă "xor" pe biți.

Cerința

După câteva meciuri, au observat că Ștefan este mult mai slab la acest joc așa că Tudor s-a gândit să îi dea un avantaj. El are la dispoziție $K$ schimbări. Dacă acesta folosește o schimbare, cei doi fac schimb de table.

Care este numărul maxim de puncte pe care îl poate acumula Ștefan folosind cel mult $K$ schimbări?

Date de intrare

Pe prima linie a fișierului de intrare skill-issue.in se vor găsi patru numere naturale nenule, $N$, $M$ și $K$.
Pe următoarele $N$ linii se vor afla câte $M$ numere naturale reprezentând configurația inițială a tablei $A$.
Pe următoarele $N$ linii se vor afla câte $M$ numere naturale reprezentând configurația inițială a tablei $B$.
Pe următoarea linie se va afla numărul $Q$.
Pe următoarele $3 \cdot Q$ linii se va afla configurația fiecărei runde:

Pe prima linie numărul natural nenul $tip$.

Dacă tip = $1$, pe următoarele $2$ linii se vor afla:

• $x_A,y_A,val_1$
• $x_B,y_B,val_2$

Dacă tip = $2$, pe următoarele $2$ linii se vor afla:

• $x_1, y_1, x_2, y_2$
• $x_3, y_3, x_4, y_4$

Date de ieșire

Pe prima linie a fișierului de ieșire skill-issue.out se va găsi un singur număr natural, numărul maxim de puncte acumulat de Ștefan efectuând maxim $K$ schimbări.

Restricții și precizări

• $1 \leq N \leq 2000$;
• $1 \leq M \leq 2000$;
• $1 \leq x_1 \leq x_2 \leq N$;
• $1 \leq y_1 \leq y_2 \leq M$;
• $1 \leq K \leq 5000$;
• $1 \leq Q \leq 5000$;
• $tip = 1$ sau $2$;
• se garantează că toate numerele sunt naturale $< 10^{18}$
• Ștefan are inițial tabla $A$, iar Tudor tabla $B$!

Exemplul 1

skill-issue.in

3 3 0
4 8 7
2 3 4
7 7 8
5 3 0
0 2 5
0 3 9
5
2
2 2 3 3
1 2 2 3
2
1 1 3 1
1 1 1 2
1
1 1 8
2 2 7
1
1 2 6
1 1 5
2
1 1 3 3
1 1 3 3

skill-issue.out

2

Explicație

• Prima rundă:

Se determină $P_A = 3 + 4 + 7 + 8 + (3 \oplus 4) + (3 \oplus 7) + (3 \oplus 8) + (4 \oplus 7) + (4 \oplus 8) + (7 \oplus 8) + (3 \oplus 4 \oplus 7) + (3 \oplus 4 \oplus 8) + (3 \oplus 7 \oplus 8) + (4 \oplus 7 \oplus 8) + (3 \oplus 4 \oplus 7 \oplus 8)) = 120$.

$P_A = P_A$ % $(10^9 + 7) = 120$.

Se determină $P_B = 3 + 0 + 2 + 5 + (3 \oplus 0) + (3 \oplus 2) + (3 \oplus 5) + (0 \oplus 2) + (0 \oplus 5) + (2 \oplus 5) + (3 \oplus 0 \oplus 2) + (3 \oplus 0 \oplus 5) + (3 \oplus 2 \oplus 5) + (0 \oplus 2 \oplus 5) + (3 \oplus 0 \oplus 2 \oplus 5)) = 56$.

$P_B = P_B$ % $(10^9 + 7) = 56.$

$P_A > P_B \rightarrow$ Stefan primeste un punct.

• A doua rundă:

se determină analog $P_A$ si $P_B$, $P_A = 28$, $P_B = 14 \rightarrow P_A > P_B \rightarrow$ Ștefan primește un punct.

• A treia rundă:

tabla $A$ devine:

8 8 7
2 3 4
7 7 8

tabla B devine:

5 3 0
0 7 5
0 3 9

• A patra rundă:

tabla $A$ devine:

8 6 7
2 3 4
7 7 8

tabla $B$ devine:

5 3 0
0 7 5
0 3 9

• A cincea rundă:

se determină analog $P_A$ si $P_B$, $P_A = 3840$, $P_B = 3840 \rightarrow P_A = P_B \rightarrow$ Nimeni nu primește niciun punct.

În final, Ștefan va avea $2$ puncte acumulate.

Exemplul 2

skill-issue.in

3 3 1
5 3 0
0 2 5
0 3 9
4 8 7
2 3 4
7 7 8
5
2
2 2 3 3
1 2 2 3
2
1 1 3 1
1 1 1 2
1
1 1 8
2 2 7
1
1 2 6
1 1 5
2
1 1 3 3
1 1 3 3

skill-issue.out

1

Explicație

Acest exemplu este similar însă acum Tablele au configurațiile interschimbate. Ștefan are o schimbare la dispoziție pe care o poate folosi să "fure" $1$ punct și să rămână cu Tabla $B$.