Junk Problem

서로 다른 두 원소의 XOR 값이 모두 다르게 되는 {1,...,n}의 부분집합 S를 크기 floor(sqrt(0.5n)) 이상으로 구성한다.

어려움9수학조합론비트 연산그리디아직 제출이 없습니다시간 제한1초메모리 제한512 MB

문제 설명

예제1

Browsing Wikipedia and reading some random references are the best way to write problems.

Find a subset S ∈ {1, 2, . . . , n} such that:

For all pairs (a, b) such that a, b ∈ S and a < b, the values of bitwise XOR of a and b should be distinct.
|S| ≥ ⌊√(0.5n)⌋.

The first line contains an integer n (1 ≤ n ≤ 107).

The first line contains an integer m: the size of S.

The second line contains m distinct integers from 1 to n: the elements of the set S in any order.