Contest Duration: - (local time) (100 minutes) Back to Home
Official

## C - Bingo 2 Editorial by en_translator

For each square, write the turn in which the square is marked. (If the square is never marked, write $$\mathrm{inf}$$ instead.) Then, the turn in which a line (row, column, or (anti)diagonal line) achieves Bingo equals the maximum of the numbers written on the line. Check all lines to find which turn Bingo will be achieved, and print the minimum among them. The complexity is $$O(N^2+T)$$.

N, T = map(int, input().split())
A = list(map(lambda x: int(x) - 1, input().split()))
inf = 1 << 30
mat = [[inf] * N for i in range(N)]

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

ans = inf

# row
for x in range(N):
mx = 0
for y in range(N):
mx = max(mx, mat[x][y])
ans = min(ans, mx)

# column
for y in range(N):
mx = 0
for x in range(N):
mx = max(mx, mat[x][y])
ans = min(ans, mx)

# (anti)diagonal
for x, y, dx, dy in [[0, 0, 1, 1], [0, N - 1, 1, -1]]:
mx = 0
for _ in range(N):
mx = max(mx, mat[x][y])
x += dx
y += dy
ans = min(ans, mx)

if ans == inf:
ans = -1
print(ans)


posted:
last update: