Submission #67852

#	Time	Username	Problem	Language	Result	Execution time	Memory
67852		cdemirer	XOR Sum (info1cup17_xorsum)	C++17	18 / 100	148 ms	4452 KiB

xorsum

#include <bits/stdc++.h>
#include <limits>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef pair<double, double> dodo;
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)


int N;
int arr[1000000];

void solve1() {
	int ans = 0;
	for (int i = 0; i < N; i++) {
		for (int j = i; j < N; j++) {
			ans ^= arr[i]+arr[j];
		}
	}
	cout << ans << endl;
}

int cnt1[4001] = {0};
int cnt2[8001] = {0};
void solve2() {
	for (int i = 0; i < N; i++) cnt1[arr[i]]++;
	/*for (int i = 0; i < 4001; i++) {
		if (cnt1[i]) cerr << "x " << i << " " << cnt1[i] << endl;
	}*/
	int ans = 0;
	for (int i = 1; i <= 8000; i++) {
		for (int j = 1; j <= i/2; j++) {
			if (j > 4000 || i-j > 4000) continue;
			cnt2[i] = ( cnt2[i] + cnt1[j] * cnt1[i-j] );
			if (2*j == i) cnt2[i] = cnt2[i] - (cnt1[j] * (cnt1[i-j]-1))/2;
			cnt2[i] %= 2;
		}
		//if (cnt2[i]) cerr << i << " " << cnt2[i] << endl;
		ans ^= cnt2[i] * i;
	}
	cout << ans << endl;
}

int main(int argc, char **argv) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++) cin >> arr[i];
	int mx = 0; for (int i = 0; i < N; i++) mx = max(mx, arr[i]);
	
	if (N <= 4000) solve1();
	else if (mx <= 4000) solve2();
	else exit(-1);

	return 0;
}

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