oj.uz

Submission #67852

# Submission time Handle Problem Language Result Execution time Memory
67852 2018-08-15T11:08:17 Z cdemirer XOR Sum (info1cup17_xorsum) C++17
18 / 100
 148 ms 4452 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 376 KB Output is correct
2 Correct 10 ms 376 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 4380 KB Output is correct
2 Correct 131 ms 4380 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 4380 KB Output is correct
2 Correct 131 ms 4380 KB Output is correct
3 Runtime error 122 ms 4452 KB Execution failed because the return code was nonzero
4 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 376 KB Output is correct
2 Correct 10 ms 376 KB Output is correct
3 Runtime error 21 ms 4452 KB Execution failed because the return code was nonzero
4 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 376 KB Output is correct
2 Correct 10 ms 376 KB Output is correct
3 Correct 148 ms 4380 KB Output is correct
4 Correct 131 ms 4380 KB Output is correct
5 Runtime error 122 ms 4452 KB Execution failed because the return code was nonzero
6 Halted 0 ms 0 KB -