oj.uz

Submission #362246

# Submission time Handle Problem Language Result Execution time Memory
362246 2021-02-02T10:41:51 Z SeDunion XOR Sum (info1cup17_xorsum) C++17
7 / 100
 1600 ms 4612 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 66;
//
// bit
// 2^bit
// a[i] %= 2^(bit+1)
// 1 <= a[i] <= 2^(bit+1)-1
// 2 <= a[i] + a[j] <= 2^(bit+2)-2
// 0010000000
// 0011111111
// 0110000000
// 0111111111
//
// 2^bit <= a[i] + a[j] <= 2^(bit+1)-1
// 2^(bit+1)+2^(bit) <= a[i] + a[j] <= 2^(bit+2)-1

const int LOG = 30;

int a[N], b[N];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	for (int i = 1 ; i <= n ; ++ i) cin >> a[i];
	int ans = 0;
	for (int bit = 0 ; bit < LOG ; ++ bit) {
		int parity = 0;
		for (int i = 1 ; i <= n ; ++ i) {
			b[i] = a[i] % (1 << (bit+1));
			for (int j = 1 ; j <= i ; ++ j) {
				if ((1<<bit) <= b[i] + b[j] && b[i] + b[j] <= (1<<(bit+1))-1) {
					parity ^= 1;
				}
				if ((1<<(bit+1))+(1<<bit) <= b[i] + b[j] && b[i] + b[j] <= (1<<(bit+2))-1) {
					parity ^= 1;
				}
			}
		}
		ans += parity * (1 << bit);
	}
	cout << ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 899 ms 436 KB Output is correct
2 Correct 880 ms 492 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1664 ms 4612 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1664 ms 4612 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 899 ms 436 KB Output is correct
2 Correct 880 ms 492 KB Output is correct
3 Execution timed out 1686 ms 1132 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 899 ms 436 KB Output is correct
2 Correct 880 ms 492 KB Output is correct
3 Execution timed out 1664 ms 4612 KB Time limit exceeded
4 Halted 0 ms 0 KB -