Submission #785606

#	Time	Username	Problem	Language	Result	Execution time	Memory
785606		raysh07	XOR Sum (info1cup17_xorsum)	C++17	45 / 100	1668 ms	8144 KiB

xorsum

#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define INF (int)1e18
#define f first
#define s second

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

void Solve()
{
	int n; cin >> n;
	vector <int> a(n);
	for (auto &x : a) cin >> x;

	int ans = 0;

	for (int i = 0; i <= 30; i++){
		auto b = a;
		for (auto &x : b) x %= 1 << (i + 1);

		sort(b.begin(), b.end());
		int cnt = 0;

		int l = 1 << i;
		int r = (1 << (i + 1)) - 1;
		int lol = (1 << (i + 1));

		for (auto &x : b){
			int ok = upper_bound(b.begin(), b.end(), r - x) - lower_bound(b.begin(), b.end(), l - x);
			ok += upper_bound(b.begin(), b.end(), r - x + lol) - lower_bound(b.begin(), b.end(), l - x + lol);
			cnt += ok;
			
			if ((2 * x) >> i & 1) cnt++;
		}

		cnt /= 2;
	//	cout << cnt << " ";
		if (cnt & 1) ans |= (1 << i);
	}
	cout << ans << "\n";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;

   // freopen("in",  "r", stdin);
   // freopen("out", "w", stdout);

  //  cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

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