問題一覧 > 通常問題

No.1707 Simple Range Reverse Problem

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

問題文

長さ $2N$ の数列 $X=(X_1,\ X_2,\ \dots,\ X_{2N})$ があります。はじめ、 $X$ は任意の $1 \le i \le N$ に対し、 $X_i=i,\ X_{i+N}=i$ を満たします。

長さ $2N$ の数列 $A=(A_1,\ A_2,\ \dots,\ A_{2N})$ が与えられるので、$X$ に対し以下の操作を $0$ 回以上行うことで $X$ を $A$ に一致させられるかを判定してください。

操作
  • $X_l=X_r$ が成り立つような $l,\ r\ (1\le l < r \le 2N)$ を選ぶ。そのあと、 $X_l,\ X_{l+1},\ \dots,\ X_{r-1},\ X_{r}$ をそれぞれ $X_{r},\ X_{r-1},\ \dots,\ X_{l+1},\ X_{l}$ で置き換える。

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

入力

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

$T$

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

$N$
$A_1$ $A_2$ $\dots$ $A_{2N}$
  • $1 \le T \le 100$
  • $1 \le N \le 1000$
  • $1 \le A_i \le N$
  • 全テストケースにおける $N$ の総和は $1000$ 以下
  • 与えられる入力はすべて整数

出力

各テストケースについて、$X$ を $A$ に一致させられる場合は Yes と、させられない場合は No と $1$ 行に出力してください。

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

サンプル

サンプル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$ 回行うことで $X$ を $A$ に一致させることができます。

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

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

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