# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
67966 | 2018-08-15T15:55:06 Z | MrTEK | XOR Sum (info1cup17_xorsum) | C++14 | 1600 ms | 16056 KB |
#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 pw(n) (1 << (n)) #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,a[N],mark[N],ans; pii b[N],nb[N]; int main() { scanf("%d",&n); for (int i = 1 ; i <= n ; i++) { scanf("%d",&a[i]); b[i] = mp(a[i] & 1,i); } sort(b + 1, b + n + 1); b[n + 1] = mp(INF,0); 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 = r3; while(r2 > 1 && b[l].fi + b[r2 - 1].fi >= pw(i + 1)) r2--; r1 = r2; while(r1 > 1 && b[l].fi + b[r1 - 1].fi >= pw(i)) r1--; cnt += max(0,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
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 357 ms | 4344 KB | Output is correct |
2 | Correct | 536 ms | 4456 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1690 ms | 16056 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1690 ms | 16056 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 357 ms | 4344 KB | Output is correct |
2 | Correct | 536 ms | 4456 KB | Output is correct |
3 | Execution timed out | 1674 ms | 16056 KB | Time limit exceeded |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 357 ms | 4344 KB | Output is correct |
2 | Correct | 536 ms | 4456 KB | Output is correct |
3 | Execution timed out | 1690 ms | 16056 KB | Time limit exceeded |
4 | Halted | 0 ms | 0 KB | - |