4197 - AB

Alice tocmai s-a decis să-și impresioneze fratele mai mic, Bob, cu abilitățile sale de deducție matematică. Astfel, ea așează într-o matrice cu N linii și M coloane toate numerele 1, 2, …, N × M, astfel încât fiecare linie și respectiv fiecare coloană, să fie sortată strict crescător. O matrice cu aceste proprietăți se numește o matrice AB. Alice îi cere apoi lui Bob să elimine K valori din matrice, care sa nu fie adiacente orizontal sau adiacente vertical. Apoi, ea va încerca să reintroducă aceste K valori în matrice astfel încât sa rămână o matrice AB. După câteva încercări, Alice realizează că, în anumite situații pot exista mai multe moduri de a aranja cele K numere pe pozițiile libere.

Cerința

Scrieți un program care, cunoscând matricea AB inițială și Q interogări, constând fiecare dintr-o listă de elemente eliminate din matrice, determină pentru fiecare interogare dacă există o soluție unică de a aranja elementele eliminate în matrice astfel încât aceasta să fie matrice AB.

Date de intrare

Prima linie a datelor de intrare conține trei numere naturale N, M și Q, separate prin câte un spațiu, având semnificația din enunț. Pe următoarele N linii se află câte M valori, separate prin câte un spațiu, reprezentând matricea AB construită de Alice. Urmează apoi Q interogări, fiecare interogare fiind descrisă pe două linii. Prima linie care descrie o interogare conține numărul natural K, reprezentând numărul de valori eliminate de către Bob. Pe a doua linie din descrierea interogării se află cele K numere eliminate, separate prin câte un spațiu.

Date de ieșire

Veți afișa Q linii, fiecare reprezentând un număr întreg. Cea de a i-a linie va conține răspunsul pentru a i-a interogare: răspunsul va fi 1 dacă există o soluție unică de a aranja elementele eliminate astfel încât să se obțină o matrice AB, respectiv 0 în caz contrar.

Restricții și precizări

• 1 ≤ N, M ≤ 2.000
• 1 ≤ Q ≤ 25
• K ≥ 1
• Se garantează că în orice interogare numerele eliminate sunt distincte și respectă condiția din enunț (nu sunt adiacente orizontal sau vertical).
• Numărul total al valorilor din interogări nu depășește 4.000.000.
• Punctajul pentru un test va fi acordat doar dacă răspunsurile pentru toate interogările din testul respectiv sunt corecte.
• Datorită dimensiunilor mari ale datelor de intrare, doar unele teste au fost adăugate.

Exemplu:

Intrare

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

Ieșire

1
0

Explicație

Prima interogare presupune eliminarea numerelor 1, 5 și 9, matricea după eliminare arătând astfel:

? 2 4

3 ? 8

6 7 ?

Se observă că aranjarea celor trei numere este unică, obținându-se matricea originală.

A doua interogare presupune eliminarea valorilor 5, 4 și 6:

1 2 ?

3 ? 8

? 7 9

Rearanjarea nu este unică, o soluție alternativă fiind:

1 2 5

3 6 8

4 7 9

def is_unique_solution(N, M, queries):
    results = []
    for query in queries:
        if len(query) == 0:
            results.append("YES")
            continue
        
        positions = [(val - 1) // M, (val - 1) % M for val in query]
        sorted_query = sorted(query)
        
        for i in range(1, len(sorted_query)):
            pos1 = positions[sorted_query[i-1] - 1]
            pos2 = positions[sorted_query[i] - 1]
            
            if pos1[0] == pos2[0] and pos1[1] + 1 == pos2[1]:
                results.append("NO")
                break
            if pos1[1] == pos2[1] and pos1[0] + 1 == pos2[0]:
                results.append("NO")
                break
        else:
            results.append("YES")
    
    return results

# Example usage:
N, M = 3, 3
queries = [
    [5, 7, 9],
    [1, 3, 6],
    [2, 4, 8]
]
print(is_unique_solution(N, M, queries))