J - Median Operations Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 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 のときはそのような操作列が存在しません。