| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 129 | 64 | 53 | 55.208% |
You are given $n$ non negative integers $a_1, a_2, \dots , a_n$ less than 2ドル^m$. For each of them you are to find the maximum possible hamming distance between it and some other element of the array $a$.
The hamming distance of two non negative integers is defined as the number of positions in the binary representation of these numbers in which they differ (we add leading zeros if necessary).
Formally, for each $i$ calculate: $$\max_{1 \le j \le n}hamming(a_i, a_j)$$
The first line contains two integers $n$ and $m$ (1ドル ≤ n ≤ 2^m,ドル 1ドル ≤ m ≤ 20$).
The second line contains $n$ numbers $a_i$ (0ドル ≤ a_i < 2^m$)
Output $n$ numbers seperated with spaces, where the $i$-th number is the maximum hamming distance between $a_i$ and some other number in $a$.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 20 | $m ≤ 10$ |
| 2 | 25 | $m ≤ 16$ |
| 3 | 25 | No additional constraints. |
4 4 9 12 9 11
2 3 2 3
4 4 5 7 3 9
2 3 2 3
4 4 3 4 6 10
3 3 2 3
Clarification of the third example: The numbers 3ドル,ドル 4ドル,ドル 6ドル,ドル 10ドル$ can be represented as 0011ドル,ドル 0100ドル,ドル 0110ドル,ドル 1010ドル,ドル in binary. Numbers 3ドル$ and 4ドル$ differ at 3ドル$ places, same as numbers 4ドル$ and 10ドル$. On the other hand, the number 6ドル$ differs in at most 2ドル$ places with all other numbers.