[BOJ 16685 // C++] XOR 포커

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 16685번 문제인 XOR 포커이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/16685 

16685번: XOR 포커

\(x_i\)들을 짝수개 xor한 값은 항상 \(x_1\oplus x_i\)들의 xor로 다시 나타낼 수 있음을 관찰하자. 구체적으로 \(x_1\)을 포함하는 짝수개의 \(x_i\)들의 xor값은 1보다 큰 선택한 (총 홀수개의) 인덱스 \(i\)에 대하여 \(x_1\oplus x_i\)들을 xor한 것으로 나타낼 수 있고, \(x_1\)을 포함하지 않는 짝수개의 \(x_i\)들의 xor은 선택한 (총 짝수개의) 인덱스 \(i\)에 대하여 \(x_1\oplus x_i\)들을 xor한 것으로 나타낼 수 있다.

 

위의 내용과 11191번 문제의 풀이법을 이용해 주어진 문제를 해결하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

int N;
ll arr[100000];

ll mx = 0;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++) cin >> arr[i];
	for (int i = 1; i < N; i++) arr[i] ^= arr[0];

	ll dgt = (1LL << 60);
	while (dgt) {
		int idx = 1; ll ival;
		for (; idx < N; idx++) {
			if (arr[idx] & dgt) {
				ival = arr[idx];
				if ((mx & dgt) == 0) mx ^= ival;
				break;
			}
		}
		for (; idx < N; idx++) {
			if (arr[idx] & dgt) arr[idx] ^= ival;
		}

		dgt >>= 1;
	}
	
	cout << mx;
}