← 返回题目列表

AtCoder · tupc2024_j

J. 中值运算

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

配点 : 100 点

問題文

积极奇数 N 和 按字典顺序比较 (1, 2, \ldots, N) 的排列 给出了 P = (P_1, P_2, \ldots, P_N) 。 对于

你最初有一个数列 A = P 并且对于数列 A 可以重复进行以下操作。

  • A 选择长度为奇数的连续子列。将选中的连续子列的中位数 m , A 从中删除,并在该位置放入 m 。 由
    • 更准确地说, 使所有 1 \leq l \leq r \leq |A| 和 r-l+1 是奇数的整数对 (l, r) 。 (A_l, A_{l+1}, \ldots, A_r) 的中位数 m , A 该值应乘以 (A_1, \ldots, A_{l-1}, m, A_{r+1}, \ldots, A_n) 。

各 k = 1, 2, \ldots, N 关于 A 是长度 它在两个方向上都与 1 序列 使用 (k) 。 您将获得

T 测试用例,因此请逐一回答。

制約

  • 1 \leq T \leq {10}^4
  • 3 \leq N \leq 2 \times {10}^5
  • N 是奇数
  • (P_1, P_2, \ldots, P_N) 是 您也可以写 (1, 2, \ldots, N) 的排列 给出了
  • 1 包含在输入文件中的 N 的总和是 2 \times {10}^5 以下
  • 所有输入均为整数

部分点

  • 额外约束“ 1 包含在输入文件中的 N 的总和是 5000 以下」满足的数据集答对时 10 点。 如果您正确回答了所有满足

入力

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

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

这里 \text{case}_i 是 您也可以写 i 个测试用例,每个测试用例按以下格式给出。

N
P_1 P_2 \ldots P_N

出力

T 行。

i 在线 i 个测试用例的答案以长度为 N 的字符串输出。 字符串的 k 个字符,如果通过重复操作可以使数列 (k) 变为 1 ,否则 对于第 0 。


入力例 1

2
5
2 3 1 5 4
7
7 6 3 4 5 2 1

出力例 1

00110
0101010

1 个测试用例关于

  • k = 3 时 : (l, r) = (1, 5) 选择 A = (3) 。
  • k = 4 时 : (l, r) = (1, 3) 选择 A = (2, 5, 4) 之后变为 (l, r) = (1, 3) 选择 A = (4) 。
  • k = 1, 2, 5 的时候不存在那样的操作序列。