hckim

문제링크

https://www.acmicpc.net/problem/10266

풀이

• 시계 시간이 같다는건 각 시계의 바늘들의 위치관계가 같다는 것
• $v[x]:$ x 각도에 있는지 없는지로 정의
• v1 이랑 v2 를 shift 한거랑 같을 때가 있는지 찾기
  • 는 v1 두개 붙인 배열에서 v2 찾기랑 같음

코드

• 시간복잡도: 
  • $v[x]: $ x 각도 바늘 유무로 하면 $O(360,000 * 3 + 2N)$
  • $v[i]: $ 각도 오름차순 기준으로 i + 1 번째 바늘과 i 번째 바늘의 차이로 정의하면 $O(2N + NlogN + N + 2N)$
  • 문제조건에선 첫번째로 하는게 살짝 빠름

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;
    
    vector<int> a(360000), b(360000);
    for (int i = 0; i < N; ++i) {
        int num;
        cin >> num;
        a[num] = 1;
    }
    for (int i = 0; i < N; ++i) {
        int num;
        cin >> num;
        b[num] = 1;
    }

    auto buildPi = [&](vector<int>& p) {
        int pLen = p.size();
        vector<int> pi(pLen, 0);
        for (int j = 0, i = 1; i < pLen; ++i) {
            while (j > 0 && p[i] != p[j]) j = pi[j - 1];
            if (p[i] == p[j]) ++j, pi[i] = j;
        }
        return pi;
    };
    auto kmp = [&](vector<int>& s, vector<int>& p) {
        // find p in s
        vector<int> answer;
        int sLen = s.size(), pLen = p.size();
        auto pi = buildPi(p);
        for (int j = 0, i = 0; i < 2 * sLen; ++i) {
            while (j > 0 && s[i % sLen] != p[j]) j = pi[j - 1];
            if (j == pLen - 1) answer.push_back(i % sLen - pLen + 2), j = pi[j];
            else ++j;
        }
        return answer;
    };

    auto answer = kmp(a, b);
    if (answer.size()) {
        cout << "possible\n";
    } else {
        cout << "impossible\n";
    }
}