BOJ. Clock pictures (10266)

[Link] https://www.acmicpc.net/problem/10266

한국어 · 日本語

A clock has 360,000 possible angular positions, one for each 1/1000-degree unit from 0 through 359999. Store each picture in a Boolean array of this length: an index is true exactly when a clock hand appears at that position. This representation also handles multiple hands at the same position without changing the matching logic.

The pictures match when one can be rotated to coincide with the other. Equivalently, the clockwise gaps between consecutive hands must form the same cyclic sequence in both pictures: the starting hand may differ, but the gaps must match in order. Instead of comparing those gaps under every possible starting hand, treat the first Boolean pattern as circular: concatenate it with itself. Every rotation then appears as a length-360000 window in that doubled pattern. Scan only the first 2 * 360000 - 1 positions; these contain every possible window start exactly once without including a redundant start at the duplicated endpoint. KMP checks whether the second pattern occurs in that scan.

The prefix table and scan both compare Boolean values directly, so occupied positions remain distinct from empty ones. For C = 360000 positions and N hands, building the arrays and running KMP take O(C + N) time. The position arrays and prefix table use O(C) space; the temporary input arrays use O(N), and the problem constraint N <= 200000 < C keeps the total auxiliary space at O(C).

import java.util.*;
import java.io.*;

public class Main {
    static BufferedReader br;
    static int timeNum = 360000;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        br.readLine();
        boolean[] clock1 = new boolean[2 * timeNum];
        boolean[] clock2 = new boolean[timeNum];
        int[] arr = getArr();
        for (int e : arr) clock1[e] = clock1[e + timeNum] = true;
        arr = getArr();
        for (int e : arr) clock2[e] = true;
        print(kmp(clock1, clock2) ? "possible" : "impossible");
    }

    static int[] pi(boolean[] s) {
        int[] pi = new int[s.length];
        int l = 0;
        for (int r = 1; r < s.length; r++) {
            while (l > 0 && s[l] != s[r]) l = pi[l - 1];
            if (s[l] == s[r]) {
                pi[r] = l + 1;
                l++;
            }
        }
        return pi;
    }

    static boolean kmp(boolean[] t, boolean[] s) {
        int[] pi = pi(s);
        int r = 0;
        for (int l = 0; l < 2 * timeNum - 1; l++) {
            while (r > 0 && t[l] != s[r]) r = pi[r - 1];
            if (t[l] == s[r]) {
                if (r == s.length - 1) return true;
                r++;
            }
        }
        return false;
    }

    static int toi(String s) { return Integer.parseInt(s); }
    static int[] getArr() throws IOException { return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray(); }
    static <T> void print(T s) { System.out.print(s); }
}