結果

問題 No.2490 Escalator
ユーザー Sillpherth
提出日時 2025-04-20 21:50:33
言語 Java
(openjdk 23)
結果
WA  
実行時間 -
コード長 1,912 bytes
コンパイル時間 4,189 ms
コンパイル使用メモリ 79,764 KB
実行使用メモリ 62,928 KB
最終ジャッジ日時 2025-04-20 21:51:09
合計ジャッジ時間 35,231 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21 WA * 52
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.Scanner;

public class SymmetryChecker
{
    static int[] buildLPS(int[] pattern)
    {
        int m = pattern.length;
        int[] lps = new int[m];
        int len = 0;
        for (int i = 1; i < m; )
        {
            if (pattern[i] == pattern[len])
            {
                lps[i++] = ++len;
            } else if (len > 0) {
                len = lps[len - 1];
            } else {
                lps[i++] = 0;
            }
        }
        return lps;
    }

    static boolean existsCentrallySymmetricRotation(int[] A) {
        int N = A.length / 2;
        int[] revA = new int[2 * N];
        for (int i = 0; i < 2 * N; i++) {
            revA[i] = A[2 * N - 1 - i];
        }

        int[] AA = new int[4 * N];
        for (int i = 0; i < 2 * N; i++) {
            AA[i] = A[i];
            AA[i + 2 * N] = A[i];
        }

        // KMP検索
        int[] lps = buildLPS(revA);
        int i = 0, j = 0;
        while (i < AA.length) {
        	//System.out.print(j);
            if ((AA[i] == revA[j]) || (AA[i]==-1) || (revA[j]==-1))
            {
                i++; j++;
            } else if (j > 0) {
                j = lps[j - 1];
            } else {
                i++;
            }

            if (j == revA.length)
            {
                int matchPos = i - j;
                if (matchPos >= 0 && matchPos <= 2 * N)
                {
                    return true;
                }
                j = lps[j - 1];
            }
        }

        return false;
    }

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int len = 2*sc.nextInt();
        int[] A = new int[len];
        for (int i = 0; i < len; i++)
        {
            A[i] = sc.nextInt();
        }
        boolean result = existsCentrallySymmetricRotation(A);
        System.out.println(result ? "Yes" : "No");
    }
}
0