시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 512 MB | 18 | 7 | 5 | 33.333% |
You are given an array of non-negative integers $a_1, a_2, \ldots, a_n$ and an integer $k$. Two indices $i, j$ are called inconsistent if both of the two conditions hold:
Here $\mathrm{AND}$ stands for bitwise and operation, $\mathrm{XOR}$ stands for bitwise exclusive-OR operation.
A consistent coloring of $a_1, \ldots, a_n$ in $m$ colors is an array of $n$ integers $c_1, \ldots, c_n$ ($1 \leq c_i \leq m$) such that there is no pair of inconsistent indices $i, j$ with $c_i = c_j$.
Your task is to find the smallest possible number of colors in a consistent coloring of $a_1, \ldots, a_n$.
In the first line you are given two integers $n, k$ ($1\leq n, k\leq 5\cdot 10^5$).
In the next line you are given $n$ integers $a_i$ ($0\leq a_i < 2^{22}$).
Print one integer --- the smallest number of colors in a consistent coloring.
4 1 1 2 4 6
2
One possible consistent coloring in two colors is $1, 1, 1, 2$. Since indices $2$ and $4$ are inconsistent, one color is not enough.