← 返回题目列表

AtCoder · code_thanks_festival_2015_d

D. 曝光

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

問題文

1 从 N 编号最多为 N 期末考试在一所由学生组成的学校举行。考试是 100 每个学生都获得了满分制的非负整数分数。

在这所学校,每个学生都会收到自己的分数和所有考生的总分的通知,但不会通知其他信息。

然而,每个学生都关心其他学生的成绩。因此,学生询问其他学生的分数,并使用这些值来预测其他学生的分数。

您是一名学校老师,您很好奇您的学生对其他学生分数的了解有多准确,因此您决定调查可以在多大程度上根据学生的行为确定分数。

具体如下图。 我们决定在按数字升序处理 M 信息查询或问题查询时计算问题查询的答案。

  • 查询: 它们的编号最大为 1 从 M 。任何查询 由 3 整数 a_i (0 ≦ a_i ≦ 1), b_i (1 ≦ b_i ≦ N), c_i (1 ≦ c_i ≦ N, b_i≠c_i) 定义。 当
  • a_i = 0 时,查询 i 是信息查询。这是一名学生 b_i 是一名学生 表示您知道 c_i 的分数。
  • a_i = 1 时,查询 i 是一个问题查询。这是一名学生 b_i 是查询 只需要查询 i 的信息以及他们已经知道的信息,学生 表示必须回答多少分才能判定为 c_i 的分数。

入力

输入是按以下格式从标准输入给出的。

N
s_1
s_2
:
s_N
M
a_1 b_1 c_1
a_2 b_2 c_2
:
a_M b_M c_M
  • 1 行中显示学校的学生人数 N (2 ≦ N ≦ 50) 。
  • 2 在 N 行给出了学生的分数。N 行数过多 i (1 ≦ i ≦ N) 学生 i 获得的积分 s_i (0 ≦ s_i ≦ 100) 。
  • N+2 行显示查询数量。 M (1 ≦ M ≦ 5,000) 。
  • N+3 在 M 行提供查询信息。M 行数过多 i (1 ≦ i ≦ M) 行包含查询 定义 i 一个整数 3 整数 a_i (0 ≦ a_i ≦ 1), b_i (1 ≦ b_i ≦ N), c_i (1 ≦ c_i ≦ N, b_i≠c_i) 用空格分隔。
  • 1 ≦ i < j ≦ M 对于 i, j ,a_i = a_j = 0 然后,b_i ≠ b_j 或 c_i ≠ c_j 成立。
  • 在输入中 满足 1 ≦ i ≦ M 的整数 在 i 中 a_i = 1 (即至少 1 保证有问题查询)。

出力

M 查询中的问题查询数量为 当设置 Q 时,输出为 输出第 Q 行组成。Q 行数过多 i (1 ≦ i ≦ Q) 行中,i 个问题查询的答案。 第i 个问题查询的答案是 如果答案小于x 点以上 y , 按此顺序输出x 和 我讨厌 y ,用空格分隔。还在输出末尾添加换行符。


入力例1

4
80
90
70
100
6
0 2 3
0 4 2
1 2 4
0 2 4
1 2 1
1 4 1

出力例1

80 100
80 80
50 100

学生 4 人和查询是 有 6 。

  • 查询 1 是信息查询。学生 2 是一名学生 3 的分数是 70 知道这是一个点。
  • 查询 2 是信息查询。学生 4 是一名学生 2 的分数是 90 知道这是一个点。
  • 查询 3 是一个问题查询。此时同学们 2 总分为 80+90+70+100=340 一点,学生 2 的分数是 90 一点,学生 3 的分数是 70 既然我们知道这是一个点,同学们 4 的分数是 可以看出,它位于 80 点以上 100 点下方。因此,输出 1 行是 80 100 变为。
  • 查询 4 是信息查询。学生 2 是一名学生 4 的分数是 100 知道这是一个点。
  • 查询 5 是一个问题查询。此时同学们 2 是总成绩和学生 由于我知道除 1 之外所有学生的成绩, 1 的分数恰好是 您可以看到它是一个 80 点。因此,输出 2 行是 80 80 变为。
  • 查询 6 是一个问题查询。此时同学们 4 总分为 340 一点,学生 2 的分数是 90 一点,学生 4 的分数是 100 既然我们知道这是一个点,同学们 1 的分数是 可以看出,它位于 50 点以上 100 点下方。因此,输出 3 行是 50 100 变为。

入力例2

3
25
12
31
3
1 1 2
0 1 2
1 1 2

出力例2

0 43
12 12

问题可能会发送给您已经知道其分数的人。


入力例3

7
32
19
22
25
23
17
18
11
0 1 2
0 4 5
0 1 4
0 2 3
0 2 7
1 1 5
1 2 7
1 2 1
0 4 3
1 4 2
1 6 7

出力例3

0 80
18 18
0 97
0 86
0 100