Fişierul intrare/ieşire:	dictator.in, dictator.out	Sursă	ONI 2026, Baraj Seniori, ziua 2
Autor	Toma Ariciu	Adăugată de	Bogdan Vlad-Mihai •bogdanvladmihai
Timp execuţie pe test	1.5 sec	Limită de memorie	524288 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Dictator

Allison Burgers, activist recunoscut la nivel mondial, are o armată de N · M oameni aşezaţi într-o matrice cu N linii şi M coloane. Se ştie că fiecare om de pe linia i are A_i unităţi de aladeen, iar fiecare om de pe coloana i are B_i unităţi de aladeen. Deşi teoretic aladeen şi aladeen sunt două unităţi diferite de măsură, ignorăm acest lucru şi tragem concluzia că omul aflat pe linia i şi coloana j are în total A_i + B_j unităţi de aladeen.

Deoarece Allison Burgers este o persoană foarte open-minded, el impune Q restricţii. O restricţie este definită prin coordonatele (x₁, y₁) şi (x₂, y₂) ale colţurilor stânga-sus, respectiv dreapta-jos ale unei submatrici, alături de o valoare întreagă k. Aceasta impune ca toate unităţile de aladeen din submatricea respectivă să fie ≥ k, ≤ k sau = k, în funcţie de tipul restricţiei.

Cerinţă

Cunoscând cele Q restricţii, să se determine elementele celor doi vectori A şi B cu valori cuprinse în intervalul [-10⁹, 10⁹] care respectă toate condiţiile date. Dacă există mai multe perechi de vectori care generează o matrice validă, se pot afişa oricare dintre ele. Dacă nu există nicio soluţie, se va afişa -1. Nu vreţi să aflaţi ce se întâmplă dacă nu sunt respectate restricţiile.

Date de intrare

Fişierul de intrare dictator.in conţine pe prima linie trei numere naturale N, M şi Q, separate prin câte un spaţiu. Pe următoarele Q linii sunt descrise restricţiile. Fiecare linie va conţine şase numere întregi, separate prin câte un spaţiu: type, x₁, y₁, x₂, y₂ şi k, unde:

• type = 0 înseamnă că toate valorile din submatrice trebuie să fie mai mari sau egale decât k.
• type = 1 înseamnă că toate valorile din submatrice trebuie să fie mai mici sau egale decât k.
• type = 2 înseamnă că toate valorile din submatrice trebuie să fie egale cu k.

Date de ieşire

Fişierul de ieşire dictator.out va conţine:

• Valoarea -1 pe o singură linie, dacă nu se poate construi o astfel de matrice.
• Dacă există cel puţin o soluţie validă, pe prima linie se vor afişa N numere întregi reprezentând elementele vectorului A (A₁, A₂, …, A_N), iar pe a doua linie se vor afişa M numere întregi reprezentând elementele vectorului B (B₁, B₂, …, B_M). Numerele de pe fiecare linie vor fi separate prin câte un spaţiu.

Restricţii şi precizări

• 1 ≤ N, M ≤ 1 000
• 1 ≤ Q ≤ 1 000
• -1 000 ≤ k ≤ 1 000
• Valorile afişate pentru elementele vectorilor A şi B trebuie să se afle în intervalul [-10⁹, 10⁹].
• Pentru fiecare restricţie, se garantează că 1 ≤ x₁ ≤ x₂ ≤ N şi 1 ≤ y₁ ≤ y₂ ≤ M.

Exemple

Explicaţie

Avem N=2 linii, M=2 coloane şi Q=3 restricţii. Vectorii găsiţi sunt A = [0, 2] şi B = [5, 5]. Matricea generată folosind formula A_i + B_j va arăta astfel (în fiecare celulă, A_i + B_j):

Să verificăm dacă matricea generată respectă cele 3 restricţii:

• Restricţia 1 (type=2, x₁=1, y₁=1, x₂=1, y₂=2, k=5): Elementele de pe linia 1, coloanele de la 1 la 2 trebuie să fie == 5. Elementele sunt 5 şi 5, deci condiţia este respectată.
• Restricţia 2 (type=0, x₁=2, y₁=1, x₂=2, y₂=1, k=6): Elementul de pe linia 2, coloana 1 trebuie să fie ≥ 6. Valoarea este 7, iar 7 ≥ 6, deci condiţia este respectată.
• Restricţia 3 (type=1, x₁=2, y₁=2, x₂=2, y₂=2, k=8): Elementul de pe linia 2, coloana 2 trebuie să fie ≤ 8. Valoarea este 7, iar 7 ≤ 8, deci condiţia este respectată.

Aceasta nu este singura soluţie validă. O altă soluţie acceptată ar putea fi, de exemplu, A = [2, 4] şi B = [3, 3].

Explicaţie

Trebuie să construim o matrice cu o linie şi o coloană ($N=1$, M=1). Prima restricţie impune ca unicul element să fie ≥ 10, iar a doua restricţie impune ca acesta să fie ≤ 5. Este imposibil ca un număr să respecte simultan ambele condiţii, prin urmare răspunsul este -1.

Cum se trimit solutii?