시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB114512769.231%

문제

하이비의 생일이 점점 다가오고 있다. PS를 하는 사람은 다들 알겠지만, 생일인 사람에게는 그 사람이 좋아하는 수열을 선물해줘야 한다.

하이비가 올해 받고 싶어하는 선물은 다음 조건을 만족하는 수열 A이다.

  • A는 1부터 N까지의 정수가 정확히 한 번씩 등장하는 길이 N의 수열이어야 한다.
  • A에 있는 모든 수로 이진 탐색을 수행했을 때, 정확히 K개의 수를 찾을 수 있어야 한다.
    • 즉, 아래 정의되어있는 함수 f에 대하여 f(A[1]), f(A[2]), ..., f(A[N])을 모두 시행했을 때, true가 반환되는 횟수가 정확히 K번이어야 한다.
      // C++ 이진 탐색
      bool f(int x){
          int l = 1, r = N;
          while (l <= r){
              int mid = (l+r) / 2;
              if (A[mid] == x){ return true; } // 값이 중앙값과 같으면 '찾았음'으로 판정
              if (x < A[mid]){ r = mid-1; }    // 값이 중앙값보다 작으면 [l, mid) 구간을 탐색
              if (A[mid] < x){ l = mid+1; }    // 값이 중앙값보다 크면 (mid, r] 구간을 탐색
          }
          return false;                        // [l, r] 구간에 남은 수가 없다면 '찾지 못함'으로 판정
      }

하이비의 친구 바이히는 위 조건을 만족하는 수열 A를 선물하기로 했으나, 이를 손으로 직접 만들기는 귀찮아서 프로그램을 사용해 수열을 만들기로 했다. 하지만 PS 초보인 바이히는 결국 그러한 프로그램을 만드는 데 실패했고, 당신에게 도움을 청해왔다.

바이히를 위해 NK가 주어질 때, 하이비에게 선물로 줄 수 있는 수열 A를 아무거나 하나 만들어주자.

입력

첫째 줄에 양의 정수 NK가 주어진다. (1 ≤ KN ≤ 1,000,000)

출력

만약 조건을 만족하는 수열이 존재한다면 첫째 줄에 "YES"를 출력하고, 둘째 줄에 그러한 수열 중 아무거나 하나를 출력한다. 만약 조건을 만족하는 수열이 존재하지 않는다면 첫째 줄에 "NO"를 출력한다.

예제 입력 1

5 3

예제 출력 1

YES
1 5 2 4 3

수열의 각각의 원소에 이진 탐색을 돌린 결과는 다음과 같다.

  • A1 = 1: [1, 5] → [1, 2] → '찾았음'
  • A2 = 5: [1, 5] → [4, 5] → [5, 5] → [6, 5] → '찾지 못함'
  • A3 = 2: [1, 5] → '찾았음'
  • A4 = 4: [1, 5] → [4, 5] → '찾았음'
  • A5 = 3: [1, 5] → [4, 5] → [4, 3] → '찾지 못함'

예제 입력 2

2 1

예제 출력 2

YES
2 1

노트

이 문제에서 이진 탐색이 위와 같이 정의된 이유는 하이비가 저 방식으로 이진 탐색을 구현하기 때문이다.

출처