제출 #207377

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
207377		Mucosolvan	XOR Sum (info1cup17_xorsum)	C++14	0 / 100	1700 ms	88568 KiB

xorsum

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
ordered_set;	

#define FOR(i,a,b) for(int i = (a); i <= (b); ++i)
#define FORD(i,a,b) for(int i = (a); i >= (b); --i)
#define RI(i,n) FOR(i,1,(n))
#define REP(i,n) FOR(i,0,(n)-1)
#define mini(a,b) a=min(a,b)
#define maxi(a,b) a=max(a,b)
#define mp make_pair
#define pb push_back
#define st first
#define nd second
#define sz(w) (int) w.size()
typedef vector<int> vi;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> para;
const ll inf = 1e18 + 7;
const ll maxN = 1e6 + 5;
//const ll MOD = 1e9 + 7;

int n, arr[maxN];
int antiMods[10 * maxN], cnt[10 * maxN], prefSum[maxN];

ll check(int l, int r, int x, vi& vec) {
	auto it = lower_bound(vec.begin(), vec.end(), l);
	if (it == vec.end() || *it > r) return 0;
	int leftMod = antiMods[*it];
	it = lower_bound(vec.begin(), vec.end(), r);
	if (it == vec.end() || *it > r) {
		if (it == vec.begin()) return 0;
		it--;
	}
	int rightMod = antiMods[*it];
	
	//cout << i << " " << x << " " << leftMod << " " << rightMod << endl;
	int whatevs = 0;
	if (leftMod > 0) whatevs = prefSum[leftMod - 1];
	ll sum = (prefSum[rightMod] - whatevs) * cnt[x];
	if (l <= x && x <= r) {
		sum -= cnt[x];
	}
	return sum;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin >> n;
	int res = 0;
	REP(i, n) cin >> arr[i];
	REP(i, 25) {
		//i-ty bit sprawdzamy
		int MOD = (1 << (i + 1));
		vi vec, tmp;
		REP(j, n) {
			tmp.pb(arr[j] % MOD);
			cnt[arr[j] % MOD] = 0;
		}
		sort(tmp.begin(), tmp.end());
		for (auto x: tmp) {
			if (cnt[x] == 0) vec.pb(x);
			cnt[x]++;
		}
		sort(vec.begin(), vec.end());
		REP(j, sz(vec)) {
			antiMods[vec[j]] = j;
			prefSum[j] = cnt[vec[j]];
			if (j > 0) prefSum[j] += prefSum[j - 1];
		}
		ll ans = 0;
		REP(j, sz(vec)) {
			// chcemy zeby 2^(b + 1) > x + y >= 2^b
			int x = vec[j];
			int r = MOD - x - 1;
			int l = max(0, MOD / 2 - x);
			ll sum = check(l, r, x, vec);
			ans += sum;
			if (x > MOD / 2) {
				l = MOD + MOD / 2 - x;
				r = MOD - 1;
				ans += check(l, r, x, vec);
			}
		}
		ans /= 2;
		if (ans % 2) {
			res += (1 << i);
		}
		//cout << endl;
	}
	cout << res;
	return 0;
}

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