시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 311 | 146 | 118 | 54.128% |
진벽이와 미야는 XOR 포커라는 게임을 하고 있다. 서로 정수가 적힌 카드를 N장 받고, 받은 카드 중 일부를 적절히 골라 점수를 계산하여 점수가 더 높은 쪽이 이기는 게임이다.
점수를 계산하는 방법은 다음과 같다.
예를 들어서, 미야가 현재 {1, 2, 3, 3, 5} 가 적힌 카드를 가지고 있다고 하자. {2, 3, 3, 5} 을 고르면 2 $\oplus$ 3 $\oplus$ 3 $\oplus$ 5 = 7이 점수가 된다. 똑같이 7이 되는 {1, 3, 5} 는 홀수개이기 때문에 고를 수 없다.
미야는 승부욕이 강해서 진벽이를 꼭 이기고 싶다. 미야가 승부에서 이길 수 있도록 도와주자.
첫 번째 줄에는 미야가 가진 카드의 개수 N 이 주어진다. (2 ≤ N ≤ 100,000)
두 번째 줄부터 N개의 줄에 걸쳐 미야의 i 번째 카드에 적힌 수 ai가 주어진다. (0 ≤ ai ≤ 1018)
첫 번째 줄에 미야가 주어진 카드 XOR 포커를 할 때 만들 수 있는 점수의 최댓값을 출력한다.
5 1 2 3 3 5
7
4 8 2 4 1
15
7 765 876 961 315 346 825 283
1010
양의 정수들 x1, x2, ..., xN 의 XOR 값은 다음과 같이 정의된다.
XOR 값을 X라고 하자. X를 이진법으로 나타낼 때, x1, x2, ..., xN 중 2k의 자리가 1인 수가 홀수 개 있으면 X의 2k의 자리는 1이며, 짝수 개 있으면 0이다.
University > 고려대학교 > 2018 고려대학교 프로그래밍 경시대회 (KCPC) > Advanced Div. E번
University > 고려대학교 > 2018 고려대학교 프로그래밍 경시대회 (KCPC) > Intermediate Div. H번