18762번 - Junk Problem 스페셜 저지다국어

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 ≤ 10⁷).

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.