연습문제

[한양대 HCPC 2023] XNOR의 반란

난이도
Lv. 5
제출
24 명
참가자
9 명
정답률
0.00 %
지원 언어
C
C++
Java
Python
JavaScript
언어별 시간/메모리
언어별 시간/메모리 표
언어 시간 메모리
C++ 1초 1024MB
JavaScript 5초 1024MB
C 1초 1024MB
Java 3초 1024MB
Python 5초 1024MB

PS 문제에는 항상 XOR만 사용된다는 점에 분노한 XNOR이 음이 아닌 정수 N개를 모아 반란을 일으키기로 했다!


XNOR은 체계적이기 때문에, 반란을 일으키기 전 반란의 강도를 계산해 보기로 했다. XNOR이 일으키는 반란이기 때문에, 반란의 강도는 주어진 수를 앞에서부터 차례로 XNOR한 결과가 된다. XNOR이 모은 정수들은 모두 부호 없는 B비트 정수로 표현할 수 있기 때문에, B비트 정수 간의 XNOR을 사용한다.


반란의 강도가 높을수록 성공할 확률이 높아지기 때문에, XNOR은 N개의 수 중 하나 이상의 수를 선택해서 반란의 강도를 최대화하기로 했다. 이때 선택된 수의 순서를 바꿀 수는 없다.


노트:


두 수의 Bitwise XNOR 연산은 두 수를 이진수로 변환한 뒤, 각 비트를 비교하여 같으면 1, 다르면 0을 비트별로 계산하는 연산이다. 예로, 1100(2) XNOR 0110(2) = 0101가 된다.

제약조건

1 ≤ N ≤ 200,000

1 ≤ B ≤ 60

입력형식

첫 번째 줄에 XNOR이 모은 수의 개수 N과, XNOR이 사용하는 비트의 수 B가 공백으로 구분되어 주어진다.

두 번째 줄에 XNOR이 모은 N개의 음이 아닌 정수 A1,A2,…,AN이 10진수의 형태로 공백으로 구분되어 주어진다. (0 ≤ Ai < 2B)

출력형식

첫 번째 줄에 XNOR이 만들어 낼 수 있는 최대 반란의 강도를 출력한다.

입력예제1

5 3
1 2 3 4 5
출력예제1

7

XNOR이 [2, 3, 4, 5]를 선택하면, ((2 XNOR 3) XNOR 4) XNOR 5 = 7이 된다.

 3비트 정수이므로, 23−1 = 7보다 더 큰 수를 만들 수는 없다.

입력예제2

1 60
1217
출력예제2

1217

하나 이상의 수를 선택해야 하므로, 가능한 경우가 하나밖에 없다.

목록