뚜따와 알람시계

어떤 선택의 OR 결과를 $Y$라고 하자. 우리가 원하는 것은 $Y \le M$인 가능한 $Y$ 중 최댓값이다.

정수의 크기 비교를 이진수로 생각해 보자. $Y \le M$이 되려면 다음 중 하나이다.

• $Y = M$.
• 가장 높은 차이 나는 비트 $b$에서 $M$은 $1$, $Y$는 $0$이고, 그보다 높은 비트들은 모두 같다.

두 번째 경우, $b$보다 낮은 비트들은 무엇이든 가능하다. 따라서 $Y \le M$인 모든 값 $Y$는 다음 형태의 값 중 하나의 bitwise submask이다.

• $M$.
• $M$의 어떤 켜진 비트 $b$를 $0$으로 바꾸고, 그보다 낮은 비트들을 모두 $1$로 바꾼 값.

이러한 후보 mask를 $B$라고 하자. 어떤 선택의 OR 결과가 $B$의 submask가 되려면, 선택한 모든 $A_i$ 역시 $B$의 submask여야 한다. 즉 다음 조건을 만족해야 한다.

$$(A_i \operatorname{OR} B) = B$$

어떤 $B$에 대해 이 조건을 만족하는 $A_i$들만 골라 OR하면, 결과는 여전히 $B$의 submask이므로 $B$ 이하이고, 따라서 $M$ 이하이다. 또한 OR 연산은 원소를 더 선택해도 값이 감소하지 않으므로, 고를 수 있는 들을 모두 고르는 것이 해당 안에서 최적이다.

따라서 모든 후보 mask $B$에 대해 다음 값을 계산한다.

$$\bigvee_{\,(A_i \operatorname{OR} B) = B} A_i$$

조건을 만족하는 $A_i$가 하나 이상 있는 후보들 중 이 값의 최댓값이 정답이다. 어떤 후보에서도 하나 이상 고를 수 없다면 $-1$을 출력한다.

후보 mask의 수는 최대 $60$개이고, 각 후보마다 $N$개의 수를 확인하므로 시간 복잡도는 $O(60N)$이다. 추가 메모리 사용량은 입력 배열을 제외하면 $O(60)$이다.