문제 조건

입력 : k (1 ~ k 까지의 카드가 주어짐)

조건 1 : 뽑은 카드들에 적힌 수를 모두 ⊕한 값이 최대가 되어야 한다. ⊕는 배타적 논리합(xor)을 의미한다.

조건 2 : 첫 번째 조건에 맞게 카드를 뽑는 방법이 여러 가지인 경우, 카드를 최대한 적게 뽑아야 한다.

조건 3 : 두 번째 조건에 맞게 카드를 뽑는 방법이 여러 가지인 경우, 사전 순으로 가장 앞서도록 뽑아야 한다.

출력 : 첫 째 줄에 k 출력,

둘째 줄부터 조건을 만족하는 K개의 카드에 적힌 양의 정수를 한 줄에 하나씩 오름차순으로 출력

가능한 답이 여러 경우라면, 사전 순으로 가장 앞서는 것을 출력

문제 해결 Key_point

• 비트 마스크
• 애드 훅
• 수학

문제 해결 아이디어

1. 사전에 학습한 비트 마스크 활용을 조합하여 사용
2. 크기가 클 수 있으니 long long 형으로 M 정의

#include <iostream>
using namespace std;

void solve()
{
    long long N;
    cin >> N;
    long long M = 1;

    while (M < N) 
        M = M * 2 + 1;

    if (M == N) {
        cout << 1 << endl;
        cout << N << endl;
    } else {
        cout << 2 << endl;
        cout << (M ^ N) << endl;
        cout << N << endl;
    }
}

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

    solve();
    return 0;
}