問題一覧 > 通常問題

No.2254 Reverse Only

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 54
作問者 : noya2 / テスター : shobonvip 👑 Nachia
3 ProblemId : 9150 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-03-24 19:06:32

問題文

長さ NN の整数列 A=(A1,A2,…,AN),B=(B1,B2,…,BN)A=(A_1,A_2,\dots ,A_N),B=(B_1,B_2,\dots ,B_N) と正整数 kk が与えられます。

次の操作を 00 回以上行って AA を BB に一致させられるか判定してください。

  • 1≤l≤r≤N,r−l+1≥k1\le l\le r\le N, r - l + 1 \ge k を満たす整数 l,rl,r を選ぶ。
  • AA の ll 項目から rr 項目までを反転させる。 つまり、Al,Al+1,…,Ar−1,ArA_l,A_{l+1},\dots ,A_{r-1},A_r を Ar,Ar−1,…,Al+1,AlA_r,A_{r-1},\dots ,A_{l+1},A_l で同時に置き換える。

    • 制約

  • 入力はすべて整数
  • 1≤N≤2×1051\le N\le 2\times 10^5
  • 1≤k≤2×1051\le k\le 2\times 10^5
  • 1≤Ai,Bi≤2×105 (1≤i≤N)1\le A_i,B_i\le 2\times 10^5\ (1\le i\le N)

    • 入力

    NN kk
A1A_1 A2A_2 …AN\dots A_N
B1B_1 B2B_2 …BN\dots B_N

    出力

    操作を 00 回以上行って AA を BB に一致させられるなら Yes を、そうでないなら No を出力してください。

    サンプル

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

    22 回の操作で一致させられます。

    11 回目は l=1,r=3l=1,r=3 とします。22 回目は l=2,r=4l=2,r=4 とします。数列 AA は次のように変化します。

    3 4 1 2 →\rightarrow 1 4 3 2 →\rightarrow 1 2 3 4

    AA を BB に一致させることができるので Yes を出力します。

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

    操作することはできませんが、はじめから一致しています。

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

    一致させることはできません。

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