아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

단조증가 수열과 OR

시간 제한2초메모리 제한512 MB

요약
N-1개의 목표값이 주어질 때, 인접한 두 항의 OR이 각 목표값이 되는 비감소 수열 B가 존재하는지 판별하고 하나를 출력한다.
난이도

보통10점 중 6점

유형
비트 연산, 그리디, 구현
정답자
아직 제출이 없습니다

문제

음이 아닌 정수로 이루어진 길이 N−1N-1의 수열 A_1,A_2,⋯ ,A_N−1A\_1, A\_2, \cdots, A\_{N-1}이 주어진다.

다음 조건을 만족하는 음이 아닌 정수로 이루어진 길이 NN의 수열 BB가 존재하는지 판별하고, 존재한다면 아무 것이나 하나 출력하라.

  • (B_i(B\_i OR B_i+1)=A_iB\_{i+1}) = A\_i (1≤i≤N−1)(1 \le i \le N-1)
  • B_i≤B_i+1B\_i \le B\_{i+1} (1≤i≤N−1)(1 \le i \le N-1)

여기서 OR은 Bitwise OR 연산을 의미한다.

입력

첫 번째 줄에 수열 BB의 길이 NN이 주어진다.

그 다음 줄에 N−1N-1개의 정수 A_1,A_2,⋯ ,A_N−1A\_1, A\_2, \cdots, A\_{N-1}이 공백으로 구분되어 주어진다.

출력

만약 조건을 만족하는 수열 BB가 존재하지 않는다면 No를 출력한다.

조건을 만족하는 수열 BB가 존재한다면 첫 번째 줄에 Yes를 출력하고 그 다음 줄에 수열 BB의 각 원소를 순서대로 출력한다.

제한

  • 2≤N≤200,0002 \le N \le 200\\,000
  • 0≤A_i<2600 \le A\_i < 2^{60} (1≤i≤N−1)(1 \le i \le N-1)

예제2

  1. 예제 1

    입력
    5
    5 15 11 15
    
    예상 출력
    Yes
    1 5 10 11 15
    
  2. 예제 2

    입력
    5
    1 15 7 15
    
    예상 출력
    No