Bingo 2

题目描述

有一个 $N \times N$ 的网格，第 $i$ 行（从上往下数）第 $j$ 列（从左往右数）的单元格中包含整数 $N \times (i-1) + j$。 在 $T$ 回合内，会依次报出若干整数。在第 $i$ 回合，报出整数 $A_i$，并将包含 $A_i$ 的单元格标记。请确定第一次达成 Bingo 的回合。如果在 $T$ 回合内未达成 Bingo，则输出 $-1$。 这里，达成 Bingo 意味着满足以下至少一项条件：

存在一行，其所有 $N$ 个单元格均被标记。 存在一列，其所有 $N$ 个单元格均被标记。 存在一条对角线（从左上到右下或从右上到左下），其所有 $N$ 个单元格均被标记。

输入格式

输入从标准输入给出，格式如下： $N$ $T$ $A_1$ $A_2$ $\ldots$ $A_T$

输出格式

如果在 $T$ 回合内达成 Bingo，则输出第一次达成 Bingo 的回合号；否则，输出 $-1$。

3 5
5 1 8 9 7

4

3 5
4 2 9 7 5

-1

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

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$ $A_i \neq A_j$ if $i \neq j$. 所有输入值均为整数。网格的状态随时间变化如下。第一次在第 $4$ 回合达成 Bingo。
在五回合内未达成 Bingo，因此输出 $-1$。

标签: AtCoder|abc355C

来源

AtCoder|abc355C