Official

C - Bingo 2 Editorial by en_translator


For each row, column, or (anti)diagonal line, count the number of marked squares.

In each turn, for the lines containing the square with the current number written on it, update only the counts for those lines. It is sufficient to check only those lines if Bingo is achieved. Since there are at most four lines containing the square with the current number, this can be done in \(O(1)\) time.

The overall time complexity is \(O(N+T)\).

Sample code

N, T = map(int, input().split())
A = list(map(lambda x: int(x) - 1, input().split()))
row = [0] * N
col = [0] * N
diag = [0] * 2

for i in range(T):
    x = A[i] // N
    y = A[i] % N

    # row
    row[x] += 1
    if row[x] == N:
        print(i + 1)
        exit()

    # column
    col[y] += 1
    if col[y] == N:
        print(i + 1)
        exit()

    # diagonal
    if x == y:
        diag[0] += 1
        if diag[0] == N:
            print(i + 1)
            exit()

    # anti-diagonal
    if x + y == N - 1:
        diag[1] += 1
        if diag[1] == N:
            print(i + 1)
            exit()

print(-1)

posted:
last update: