問題一覧 > 通常問題

No.1707 Simple Range Reverse Problem

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 163
作問者 : chineristAC / テスター : hitonanode 箱星
18 ProblemId : 6832 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-10-06 17:23:32

問題文

長さ 2N の数列 X=(X1, X2, , X2N) があります。はじめ、 X は任意の 1iN に対し、 Xi=i, Xi+N=i を満たします。

長さ 2N の数列 A=(A1, A2, , A2N) が与えられるので、X に対し以下の操作を 0 回以上行うことで XA に一致させられるかを判定してください。

操作
  • Xl=Xr が成り立つような l, r (1l<r2N) を選ぶ。そのあと、 Xl, Xl+1, , Xr1, Xr をそれぞれ Xr, Xr1, , Xl+1, Xl で置き換える。

T 個のテストケースについて答えてください。

入力

はじめにテストケースの個数 T1 行目に入力で与えられます。

T

つづけて T 個のテストケースがそれぞれ以下の形式で与えられます。

N
A1 A2  A2N
  • 1T100
  • 1N1000
  • 1AiN
  • 全テストケースにおける N の総和は 1000 以下
  • 与えられる入力はすべて整数

出力

各テストケースについて、XA に一致させられる場合は Yes と、させられない場合は No1 行に出力してください。

最後に改行してください。

サンプル

サンプル1
入力
4
3
1 2 3 2 1 3
3
1 2 3 1 2 3
4
3 2 4 3 4 2 1 1
5
5 4 3 2 1 1 2 3 4 5
出力
Yes
Yes
No
No

1 つ目のテストケースについて、 X=(1, 2, 3, 1, 2, 3) の状態から l=3, r=6 として操作を 1 回行うことで XA に一致させることができます。

2 つ目のテストケースについて、 X=(1, 2, 3, 1, 2, 3) の状態ですでに XA に一致しています。

3, 4 つ目のテストケースについて、どのような操作を行っても XA に一致させられません。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。