← 返回题目列表

Codeforces · 1889/D

D. 堆栈游戏

中文机器翻译题面 查看原题

您有 $$$n$$$ 堆栈 $$$r_1,r_2,\ldots,r_n$$$。每个堆栈包含一些从 $$$1$$$ 到 $$$n$$$ 的正整数。

定义以下函数:

您想知道 $$$\texttt{init(1)}、\texttt{init(2)}、\ldots、\texttt{init(n)}$$$ 返回的值。

请注意,在这些调用期间,堆栈 $$$r_1,r_2,\ldots,r_n$$$ 不会更改,因此调用 $$$\texttt{init(1)}、\texttt{init(2)}、\ldots、\texttt{init(n)}$$$ 是独立的。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$1\le n\le 10^5$$$) — 数组 $$$r$$$ 的长度。

以下 $$$n$$$ 行中的每一行都包含几个整数。第一个整数 $$$k_i$$$ ($$$0\le k_i\le 10^5$$$) 表示第 $$$i$$$ 堆栈中的元素数量,后面的 $$$k_i$$$ 正整数 $$$c_{i,1},c_{i,2},\ldots,c_{i,k_i}$$$ ($$$1\le c_{i,j}\le n$$$) 表示第 $$$i$$$ 堆栈中的元素。 $$$c_{i,1}$$$ 是底部元素。

在每个测试中,$$$\sum k_i\le 10^6$$$。

输出

您需要输出 $$$n$$$ 值,其中第 $$$i$$$ 是 $$$\texttt{init(i)}$$$ 返回的值。

示例

输入 #1

3
3 1 2 2
3 3 1 2
3 1 2 1

输出 #1

1 2 2

输入 #2

5
5 1 2 4 3 4
6 1 2 5 3 3 4
6 1 1 4 4 4 2
9 3 1 4 2 3 5 5 1 2
4 4 4 1 3

输出 #2

1 1 1 1 1

注意

在第一个示例中:

- 当您调用 $$$\texttt{init(1)}$$$ 时,设置 $$$\texttt{stacks := [[1,2,2],[3,1,2],[1,2,1]]}$$$,然后调用 $$$\texttt{get(stacks, 1)}$$$。 $$$\texttt{stacks[1]}$$$不为空,设置$$$\texttt{new_pos := 2}$$$,并弹出$$$\texttt{stacks[1]}$$$的顶部元素,使得$$$\texttt{stacks}$$$变成$$$[[1,2],[3,1,2],[1,2,1]]$$$,然后调用$$$\texttt{get(堆栈, 2)}$$$。 $$$\texttt{stacks[2]}$$$不为空,设置$$$\texttt{new_pos := 2}$$$,并弹出$$$\texttt{stacks[2]}$$$的顶部元素,使得$$$\texttt{stacks}$$$变成$$$[[1,2],[3,1],[1,2,1]]$$$,然后调用$$$\texttt{get(堆栈, 2)}$$$。 $$$\texttt{stacks[2]}$$$不为空,设置$$$\texttt{new_pos := 1}$$$,并弹出$$$\texttt{stacks[2]}$$$的顶部元素,使得$$$\texttt{stacks}$$$变成$$$[[1,2],[3],[1,2,1]]$$$,然后调用$$$\texttt{get(堆栈, 1)}$$$。 $$$\texttt{stacks[1]}$$$不为空,设置$$$\texttt{new_pos := 2}$$$,并弹出$$$\texttt{stacks[1]}$$$的顶部元素,使得$$$\texttt{stacks}$$$变成$$$[[1],[3],[1,2,1]]$$$,然后调用$$$\texttt{get(堆栈, 2)}$$$。 $$$\texttt{stacks[2]}$$$不为空,设置$$$\texttt{new_pos := 3}$$$,并弹出$$$\texttt{stacks[2]}$$$的顶部元素,使得$$$\texttt{stacks}$$$变成$$$[[1],[],[1,2,1]]$$$,然后调用$$$\texttt{get(堆栈, 3)}$$$。 $$$\texttt{stacks[3]}$$$不为空,设置$$$\texttt{new_pos := 1}$$$,并弹出$$$\texttt{stacks[3]}$$$的顶部元素,使得$$$\texttt{stacks}$$$变成$$$[[1],[],[1,2]]$$$,然后调用$$$\texttt{get(堆栈, 1)}$$$。 $$$\texttt{stacks[1]}$$$不为空,设置$$$\texttt{new_pos := 1}$$$,并弹出$$$\texttt{stacks[1]}$$$的顶部元素,使得$$$\texttt{stacks}$$$变成$$$[[],[],[1,2]]$$$,然后调用$$$\texttt{get(堆栈, 1)}$$$。 $$$\texttt{stacks[1]}$$$为空,返回$$$1$$$。
- 当您调用 $$$\texttt{init(2)}$$$ 时,设置 $$$\texttt{stacks := [[1,2,2],[3,1,2],[1,2,1]]}$$$,然后调用 $$$\texttt{get(stacks, 2)}$$$。 $$$\texttt{stacks[2]}$$$不为空,设置$$$\texttt{new_pos := 2}$$$,并弹出$$$\texttt{stacks[2]}$$$的顶部元素,使得$$$\texttt{stacks}$$$变成$$$[[1,2,2],[3,1],[1,2,1]]$$$,然后调用$$$\texttt{get(堆栈, 2)}$$$。 $$$\texttt{stacks[2]}$$$不为空,设置$$$\texttt{new_pos := 1}$$$,并弹出$$$\texttt{stacks[2]}$$$的顶部元素,使得$$$\texttt{stacks}$$$变成$$$[[1,2,2],[3],[1,2,1]]$$$,然后调用$$$\texttt{get(堆栈, 1)}$$$。 $$$\texttt{stacks[1]}$$$不为空,设置$$$\texttt{new_pos := 2}$$$,并弹出$$$\texttt{stacks[1]}$$$的顶部元素,使得$$$\texttt{stacks}$$$变成$$$[[1,2],[3],[1,2,1]]$$$,然后调用$$$\texttt{get(堆栈, 2)}$$$。 $$$\texttt{stacks[2]}$$$不为空,设置$$$\texttt{new_pos := 3}$$$,并弹出$$$\texttt{stacks[2]}$$$的顶部元素,使得$$$\texttt{stacks}$$$变成$$$[[1,2],[],[1,2,1]]$$$,然后调用$$$\texttt{get(堆栈, 3)}$$$。 $$$\texttt{stacks[3]}$$$不为空,设置$$$\texttt{new_pos := 1}$$$,并弹出$$$\texttt{stacks[3]}$$$的顶部元素,使得$$$\texttt{stacks}$$$变成$$$[[1,2],[],[1,2]]$$$,然后调用$$$\texttt{get(堆栈, 1)}$$$。 $$$\texttt{stacks[1]}$$$不为空,设置$$$\texttt{new_pos := 2}$$$,并弹出$$$\texttt{stacks[1]}$$$的顶部元素,使得$$$\texttt{stacks}$$$变成$$$[[1],[],[1,2]]$$$,然后调用$$$\texttt{get(堆栈, 2)}$$$。 $$$\texttt{stacks[2]}$$$为空,返回$$$2$$$。
- 当您调用 $$$\texttt{init(3)}$$$ 时,设置 $$$\texttt{stacks := [[1,2,2],[3,1,2],[1,2,1]]}$$$,然后调用 $$$\texttt{get(stacks, 3)}$$$。 $$$\texttt{stacks[3]}$$$不为空,设置$$$\texttt{new_pos := 1}$$$,并弹出$$$\texttt{stacks[3]}$$$的顶部元素,使得$$$\texttt{stacks}$$$变成$$$[[1,2,2],[3,1,2],[1,2]]$$$,然后调用$$$\texttt{get(堆栈, 1)}$$$。 $$$\texttt{stacks[1]}$$$不为空,设置$$$\texttt{new_pos := 2}$$$,并弹出$$$\texttt{stacks[1]}$$$的顶部元素,使得$$$\texttt{stacks}$$$变成$$$[[1,2],[3,1,2],[1,2]]$$$,然后调用$$$\texttt{get(堆栈, 2)}$$$。 $$$\texttt{stacks[2]}$$$不为空,设置$$$\texttt{new_pos := 2}$$$,并弹出$$$\texttt{stacks[2]}$$$的顶部元素,使得$$$\texttt{stacks}$$$变成$$$[[1,2],[3,1],[1,2]]$$$,然后调用$$$\texttt{get(堆栈, 2)}$$$。 $$$\texttt{stacks[2]}$$$不为空,设置$$$\texttt{new_pos := 1}$$$,并弹出$$$\texttt{stacks[2]}$$$的顶部元素,使得$$$\texttt{stacks}$$$变成$$$[[1,2],[3],[1,2]]$$$,然后调用$$$\texttt{get(堆栈, 1)}$$$。 $$$\texttt{stacks[1]}$$$不为空,设置$$$\texttt{new_pos := 2}$$$,并弹出$$$\texttt{stacks[1]}$$$的顶部元素,使得$$$\texttt{stacks}$$$变成$$$[[1],[3],[1,2]]$$$,然后调用$$$\texttt{get(堆栈, 2)}$$$。 $$$\texttt{stacks[2]}$$$不为空,设置$$$\texttt{new_pos := 3}$$$,并弹出$$$\texttt{stacks[2]}$$$的顶部元素,使得$$$\texttt{stacks}$$$变成$$$[[1],[],[1,2]]$$$,然后调用$$$\texttt{get(堆栈, 3)}$$$。 $$$\texttt{stacks[3]}$$$不为空,设置$$$\texttt{new_pos := 2}$$$,并弹出$$$\texttt{stacks[3]}$$$的顶部元素,使得$$$\texttt{stacks}$$$变成$$$[[1],[],[1]]$$$,然后调用$$$\texttt{get(堆栈, 2)}$$$。 $$$\texttt{stacks[2]}$$$为空,返回$$$2$$$。