This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define len(a) (int)a.size()
#define fi first
#define sc second
#define left ind + ind
#define right ind + ind + 1
#define mid (l + r) / 2
#define d1(w) cerr<<#w<<":"<<w<<endl;
#define d2(w,c) cerr<<#w<<":"<<w<<" "<<#c<<":"<<c<<endl;
#define d3(w,c,z) cerr<<#w<<":"<<w<<" "<<#c<<":"<<c<<" "<<#z<<":"<<z<<endl;
#define FAST_IO ios_base::sync_with_stdio(false);
#define endl '\n'
const int maxn = 620;
const long long LINF = 1e18;
const int LOG = 31;
const int INF = 1e9 + 5;
const int N = 1e6 + 5;
const int M = 4e3 + 5;
const int SQ = 350;
const int MOD = 998244353;
typedef pair <int,int> pii;
int n,pw[N],a[N],mark[N],ans;
pii b[N],nb[N];
int main() {
scanf("%d",&n);
pw[0] = 1;
for (int i = 1 ; i < LOG ;i++) pw[i] = pw[i - 1] * 2;
for (int i = 1 ; i <= n ; i++) {
scanf("%d",&a[i]);
b[i] = mp(a[i] & 1,i);
}
sort(b + 1, b + n + 1);
memset(mark,-1,sizeof mark);
for (int i = 0 ; i < LOG ; i++) {
long long cnt = 0;
int r1 = n + 1,r2 = n + 1,r3 = n + 1;
for (int l = 1 ; l <= n ; l++) {
while(r3 > 1 && b[l].fi + b[r3 - 1].fi >= pw[i + 1] + pw[i]) r3--;
// r2 = min(r2,r3);
while(r2 > 1 && b[l].fi + b[r2 - 1].fi >= pw[i + 1]) r2--;
// r1 = min(r1,r3);
while(r1 > 1 && b[l].fi + b[r1 - 1].fi >= pw[i]) r1--;
cnt += n - r1 - (r3 - r2) + 1;
}
int say = 0;
for (int j = 1 ; j <= n ; j++) if (b[j].fi * 2 & pw[i]) say++;
cnt = (cnt + say) / 2;
if (cnt & 1) ans += pw[i];
if (i < LOG - 1) {
int last = 0;
for (int j = 1 ; j <= n ; j++) {
if (a[b[j].sc] & pw[i + 1]) mark[j] = i;
else nb[++last] = b[j];
}
for (int j = 1 ; j <= n ; j++) if(mark[j] == i) nb[++last] = mp(b[j].fi + pw[i + 1],b[j].sc);
for (int j = 1 ; j <= n ; j++) b[j] = nb[j];
}
}
printf("%d\n",ans);
return 0;
}
Compilation message (stderr)
xorsum.cpp: In function 'int main()':
xorsum.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
35 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
xorsum.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
42 | scanf("%d",&a[i]);
| ~~~~~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |