oj.uz

Submission #389469

# Submission time Handle Problem Language Result Execution time Memory
389469 2021-04-14T06:31:37 Z Kevin_Zhang_TW XOR Sum (info1cup17_xorsum) C++17
45 / 100
 195 ms 6116 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 1000010, MAX_B = 35;

int n, a[MAX_N], cnt[MAX_B];

ll sum(ll l, ll r) { return (l + r) * (r - l + 1) / 2; }

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for (int i = 0;i < n;++i)
		cin >> a[i];
	sort(a, a + n);

	for (int b = 30;b >= 0;--b) {
		if (~a[n-1]>>b&1) continue;
		DE(b, 1 << b);

		int M = 0;
		while (M < n && (~a[M]>>b&1)) ++M;

		debug(a, a + n);

		for (int i = M;i < n;++i) a[i] ^= 1<<b;
		
		
		int val = 1 << b;

		ll x = 0;

		for (int i = 0, j = n-1;i < M;++i) {
			while (j >= M && a[i] + a[j] >= val)
				--j;
			x += n - j;
		}
		//  0s,   1s
		ll A = M, B = n - M;

		cnt[b + 1] ^= (sum(1, B)) + A * B - x;

		cnt[b] ^= (A * B);

		inplace_merge(a, a + M, a + n);
	}

	int res = 0;

	for (int i = 0;i <= 30;++i) if (cnt[i] & 1) {
		DE(i);
		res |= 1 << i;
	}

	cout << res << '\n';
}

Compilation message

xorsum.cpp: In function 'int32_t main()':
xorsum.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
xorsum.cpp:33:3: note: in expansion of macro 'DE'
   33 |   DE(b, 1 << b);
      |   ^~
xorsum.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
xorsum.cpp:38:3: note: in expansion of macro 'debug'
   38 |   debug(a, a + n);
      |   ^~~~~
xorsum.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
xorsum.cpp:65:3: note: in expansion of macro 'DE'
   65 |   DE(i);
      |   ^~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 6116 KB Output is correct
2 Incorrect 174 ms 5752 KB Output isn't correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 6116 KB Output is correct
2 Incorrect 174 ms 5752 KB Output isn't correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 43 ms 868 KB Output is correct
4 Correct 42 ms 892 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 195 ms 6116 KB Output is correct
4 Incorrect 174 ms 5752 KB Output isn't correct