장난감 자물쇠

시간 제한1초메모리 제한1024 MB

요약
거리가 정확히 k인 위치끼리만 교환할 수 있을 때, 주어진 순열을 오름차순으로 정렬할 수 있는지 판별한다.
난이도

보통10점 중 5점

유형
배열, 유니온 파인드, 수학
정답자
아직 제출이 없습니다

문제

장난감 자물쇠는 주식회사 sk14cj에서 아기들의 숫자 교육을 위해 만든 특별한 자물쇠입니다.

이 자물쇠의 잠금을 해제하려면 NN개의 정수로 구성된 수열을 오름차순으로 나열해야 합니다. 이 수열에는 중복된 수 없이 00부터 N−1N-1까지의 정수가 각각 하나씩 있습니다.

평범하게 수열의 수들을 교환할 수 있으면 재미없다고 판단한 sk14cj사는, 주어진 양의 정수 kk에 대하여 수열에서 거리가 kk인 쌍만 교환할 수 있게 하였습니다. 즉, 임의의 정수 1≤i≤N−k1 \le i \le N - k에 대하여, ii번째 수와 i+ki+k번째 수를 교환할 수 있습니다. 이 때문에 수열을 오름차순으로 나열할 수 없는 불량품이 발생하기 시작했습니다.

따라서, 여러분은 장난감 자물쇠의 초기 상태를 입력받고, 불량품인지 판별하는 프로그램을 작성해야 합니다.

입력

첫 번째 줄에 수열의 길이 NN과 숫자를 서로 교환할 수 있는 간격 kk가 공백으로 구분되어 주어집니다.(2≤N≤200,000,1≤k<N)(2 \leq N \leq 200\\,000, 1 \leq k \lt N)

두 번째 줄에 장난감 자물쇠 수열의 초기 상태를 나타내는 00보다 크고 N−1N-1보다 작거나 같은 정수 A_1,A_2...A_NA\_1, A\_2 ... A\_N이 차례대로 공백으로 구분되어 주어집니다. 수열에 중복된 값은 존재하지 않으며, A_iA\_i는 자물쇠의 수열의 ii번째 값입니다.

출력

정상적인 제품일 경우 Yes를, 불량품이라면 No를 출력해주세요.

예제3

  1. 예제 1

    입력
    8 3
    0 1 2 3 4 5 6 7
    
    예상 출력
    Yes
    
  2. 예제 2

    입력
    8 2
    2 1 0 3 4 5 6 7
    
    예상 출력
    Yes
    
  3. 예제 3

    입력
    8 5
    2 1 6 3 7 0 4 5
    
    예상 출력
    No