Contest Duration: - (local time) (100 minutes) Back to Home
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: