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: