만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

수열의 개수

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

요약
주어진 N과 C에 대해 OR이 X, AND가 Y, XOR이 Z인 31비트 정수 N개 순서쌍의 수가 정확히 C가 되는 사전순 최소 (X, Y, Z)를 구하거나 존재하지 않으면 -1을 출력한다.
난이도

어려움10점 중 9점

유형
비트 연산, 조합론, 수학, 동적 계획법
정답자
아직 제출이 없습니다

문제

NN개의 수로 이루어진 수열을 생각하자. 이 수열은 아래 네 조건을 모두 만족한다.

  1. 수열의 각 수는 00 이상 231−12^{31} - 1 이하의 정수이다.
  2. 수열의 모든 수를 bitwise OR 연산한 값은 XX이다.
  3. 수열의 모든 수를 bitwise AND 연산한 값은 YY이다.
  4. 수열의 모든 수를 bitwise XOR 연산한 값은 ZZ이다.

택희는 조건을 만족하는 수열을 모두 갖고 있었지만, 이사하면서 그중 일부를 잃어버렸다. XX, YY, ZZ의 값만 알아내면 수열을 다시 전부 만들 수 있다.

택희가 기억하는 것은 두 가지다. 수열의 길이가 NN이라는 것, 그리고 네 조건을 모두 만족하는 수열이 정확히 CC개라는 것이다.

XX, YY, ZZ가 어떤 값이었을지 찾아라. 수의 순서가 다르면 서로 다른 수열로 센다.

입력

첫 줄에 수열의 길이 NN과 조건을 만족하는 수열의 개수 CC가 공백으로 구분되어 주어진다. (1≤N≤1051 \le N \le 10^5, 0≤C≤10180 \le C \le 10^{18})

출력

조건을 만족하는 수열이 정확히 CC개가 되는 00 이상 231−12^{31} - 1 이하의 정수 XX, YY, ZZ를 공백으로 구분해 첫 줄에 출력한다.

조건을 만족하는 (X,Y,Z)(X, Y, Z)가 여러 개라면 사전순으로 가장 앞서는 하나를 출력한다. 즉 XX가 가장 작은 것을 고르고, 그런 것이 여럿이면 그중 YY가 가장 작은 것을, 그래도 여럿이면 그중 ZZ가 가장 작은 것을 고른다.

그러한 XX, YY, ZZ가 없으면 −1-1 하나만 출력한다.

예제2

  1. 예제 1

    입력
    9 70110209207109375
    
    예상 출력
    127 0 0
    
  2. 예제 2

    입력
    100000 1000000000000000000
    
    예상 출력
    -1