oj.uz

Submission #785604

# Submission time Handle Problem Language Result Execution time Memory
785604 2023-07-17T10:34:56 Z raysh07 XOR Sum (info1cup17_xorsum) C++17
45 / 100
 1600 ms 20600 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 340 KB Output is correct
2 Correct 15 ms 436 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1643 ms 20600 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 1643 ms 20600 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 340 KB Output is correct
2 Correct 15 ms 436 KB Output is correct
3 Correct 427 ms 2764 KB Output is correct
4 Correct 444 ms 2772 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 340 KB Output is correct
2 Correct 15 ms 436 KB Output is correct
3 Execution timed out 1643 ms 20600 KB Time limit exceeded
4 Halted 0 ms 0 KB -