AT_abc355_c [ABC355C] Bingo 2

题目描述

有一个纵向 $N$ 行、横向 $N$ 列的网格，对于从上到下第 $i$ 行、从左到右第 $j$ 列的格子，格子中写有整数 $N \times (i-1) + j$。

接下来会进行 $T$ 个回合，每回合会宣布一个互不相同的整数。在第 $i$ 回合，会宣布 $A_i$，并在写有 $A_i$ 的格子上做标记。请你求出首次达成“宾果”（Bingo）的回合数。如果在 $T$ 个回合内都无法达成宾果，请输出 $-1$。

这里，“达成宾果”指的是以下条件至少满足一项：

• 存在某一行，该行的 $N$ 个格子全部被标记。
• 存在某一列，该列的 $N$ 个格子全部被标记。
• 存在某一条对角线，该对角线的 $N$ 个格子全部被标记。

输入格式

输入通过标准输入给出，格式如下：

$N$ $T$ $A_1$ $A_2$ $\ldots$ $A_T$

输出格式

如果在 $T$ 个回合内达成宾果，请输出首次达成宾果的回合数；否则输出 $-1$。

输入输出样例 #1

输入 #1

3 5
5 1 8 9 7

输出 #1

4

输入输出样例 #2

输入 #2

3 5
4 2 9 7 5

输出 #2

-1

输入输出样例 #3

输入 #3

4 12
13 9 6 5 2 7 16 14 8 3 10 11

输出 #3

9

说明/提示

限制条件

• $2 \leq N \leq 2 \times 10^3$
• $1 \leq T \leq \min(N^2, 2 \times 10^5)$
• $1 \leq A_i \leq N^2$
• 若 $i \neq j$，则 $A_i \neq A_j$
• 所有输入均为整数

样例解释 1

网格的状态变化如下图所示。首次达成宾果是在第 $4$ 回合。

样例解释 2

在 $5$ 个回合内无法达成宾果，因此请输出 $-1$。

由 ChatGPT 4.1 翻译