제출 #1139595

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1139595		Halym2007	XOR Sum (info1cup17_xorsum)	C++17	0 / 100	135 ms	4352 KiB

xorsum

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sz size()
#define ff first
#define ss second
#define pb push_back
#define pii pair <int, int>
#define dur exit(0)
#define dur1 return(0)
const int N = 1e6 + 5;
const int BIT = 31;
int n, a[N];
map <int, int> val, val1;
int main () {
//	freopen ("input.txt", "r", stdin);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	int jogap = 0;
	for (int bit = BIT - 1; bit >= 0; bit--) {
		// jogabyn bit-njy bit-y 1-my yada 0-my
		// ony sanamaly
		if (bit > 4) continue;
		ll sana = 0, sana1 = 0;
		for (int i = 1; i <= n; ++i) {
			if (a[i]>>bit&1) {
				int san = 0;
				san |= (1<<bit);
				for (int j = bit - 1; j >= 0; j--) {
					san <<= 1;
					san |= 1;
					if (a[i]>>j&1) {
						sana += val[san];
						san ^= 1;
					}
				}
				if (bit and (a[i] >> (bit - 1) & 1)) {
					sana++;
				}
				san = 0;
				san |= (1 << bit);
				for (int j = bit - 1; j >= 0; j--) {
					san <<= 1;
					if (a[i]>>j&1) {
						san |= 1;
						val[san]++;
					}
				}
			}
			else {
				int san = 0;
				for (int j = bit - 1; j >= 0; j--) {
					san <<= 1;
					san |= 1;
					if (a[i]>>j&1) {
						sana1 += val1[san];
						san ^= 1;
					}
				}
				if (bit and (a[i] >> (bit - 1) & 1)) {
					sana1++;
				}
				san = 0;
				for (int j = bit - 1; j >= 0; j--) {
					san <<= 1;
					if (a[i]>>j&1) {
						san |= 1;
						val1[san]++;
					}
				}
			}
			// ozunem barmaly variant bar
		}
		val.clear();
		val1.clear();
		if ((sana + sana1) % 2) {
			jogap |= (1 << bit);
		}
//		if (sana > 0) {
//			cout << bit << " " << sana << " " << sana1 << " " << sana + sana1 << "\n";
//		}
	}
	cout << jogap << "\n";
}
/*
1 1 7

ans = 12
output = 14
*/

• Subtask 1: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 38
• Subtask 5: 0 / 23