Unirea pentru Performanta - Online | skill issue

This was the problem page during the contest. Access the current page here.
Time limit: 3s Memory limit: 512MB Input: skill-issue.in Output: skill-issue.out

Ș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 NMN \cdot M, unde NN și MM sunt numere naturale nenule.

Ștefan are inițial tabla AA, iar Tudor tabla BB.

Regulile jocului:

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

Dacă runda este de tip 11 atunci:

  • se dă o căsuță (xA,yA)(x_A, y_A) a tablei AA în care numărul devine val1val_1.
  • se dă o căsuță (xB,yB)(x_B, y_B) a tablei BB în care numărul devine val2val_2.

Dacă runda este de tip 22 atunci:

  • se dau colțurile x1,y1,x2,y2x_1, y_1, x_2, y_2 unei submatrici ale tablei AA și se determină puterea PAP_A a submatricii.
  • se dau colțurile x3,y3,x4,y4x_3, y_3, x_4, y_4 unei submatrici ale tablei BB și se determină puterea PBP_B a submatricii.
  • dacă PA>PBP_A > P_B, atunci cel care este desemnat tablei AA primește un punct, iar dacă PA<PBP_A < P_B, cel care este desemnat tablei BB primește un punct. În caz de egalitate nimeni nu primește puncte.
  • Puterea PP 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 109+710^9 + 7.

Exemplu: Dacă elementele submatricii sunt 11, 22, 3P=(1+2+3+(12)+(13)+(23)+(123))3 \rightarrow P = (1 + 2 + 3 + (1 \oplus 2) + (1 \oplus 3) + (2 \oplus 3) + (1 \oplus 2 \oplus 3)) % (109+7)=12( 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 KK 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 KK schimbări?

Date de intrare

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

Pe prima linie numărul natural nenul tiptip.

Dacă tip = 11, pe următoarele 22 linii se vor afla:

  • xA,yA,val1x_A,y_A,val_1
  • xB,yB,val2x_B,y_B,val_2

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

  • x1,y1,x2,y2x_1, y_1, x_2, y_2
  • x3,y3,x4,y4x_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 KK schimbări.

Restricții și precizări

  • 1N20001 \leq N \leq 2000;
  • 1M20001 \leq M \leq 2000;
  • 1x1x2N1 \leq x_1 \leq x_2 \leq N;
  • 1y1y2M1 \leq y_1 \leq y_2 \leq M;
  • 1K50001 \leq K \leq 5000;
  • 1Q50001 \leq Q \leq 5000;
  • tip=1tip = 1 sau 22;
  • se garantează că toate numerele sunt naturale <1018< 10^{18}
  • Ștefan are inițial tabla AA, iar Tudor tabla BB!
# Punctaj Restricții
1 15 1N,M,Q5,K=01 \leq N,M,Q \leq 5, K = 0
2 35 1Q5001 \leq Q \leq 500, 1N,M3001 \leq N,M \leq 300
3 30 1N,M10001 \leq N,M \leq 1000
4 20 Fără restricții suplimentare

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ă PA=3+4+7+8+(34)+(37)+(38)+(47)+(48)+(78)+(347)+(348)+(378)+(478)+(3478))=120P_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.

PA=PAP_A = P_A % (109+7)=120(10^9 + 7) = 120.

Se determină PB=3+0+2+5+(30)+(32)+(35)+(02)+(05)+(25)+(302)+(305)+(325)+(025)+(3025))=56P_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.

PB=PBP_B = P_B % (109+7)=56.(10^9 + 7) = 56.

PA>PBP_A > P_B \rightarrow Stefan primeste un punct.

  • A doua rundă:

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

  • A treia rundă:

tabla AA 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 AA devine:

8 6 7
2 3 4
7 7 8

tabla BB devine:

5 3 0
0 7 5
0 3 9
  • A cincea rundă:

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

În final, Ștefan va avea 22 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" 11 punct și să rămână cu Tabla BB.

Log in or sign up to be able to send submissions!