# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
129320 | 2019-07-12T02:55:52 Z | TAISA_ | XOR Sum (info1cup17_xorsum) | C++14 | 1600 ms | 33896 KB |
#include<bits/stdc++.h> using namespace std; using ll=long long; using P=pair<int,int>; int main(){ cin.tie(0); ios::sync_with_stdio(0); int n;cin>>n; vector<ll> a(n); for(int i=0;i<n;i++){ cin>>a[i]; } vector<int> co(30); vector<int> v(n),id(n); for(int i=0;i<n;i++){ id[i]=i; } for(int k=0;k<30;k++){ int j=n-1; vector<int> v0,v1,s(n+1),vi0,vi1; for(int i=1;i<=n;i++){ s[i]=s[i-1]+((a[id[i-1]]>>k)&1); } for(int i=0;i<n;i++){ while(j>=0&&(1<<k)-v[i]<=v[j])--j; if((a[id[i]]>>k)&1){ if(i>j)co[k]+=s[i+1]-s[j+1]; co[k]+=min(i+1,j+1)-s[min(i+1,j+1)]; v1.push_back((1<<k)+v[i]); vi1.push_back(id[i]); }else{ if(i>j)co[k]+=(i-j)-(s[i+1]-s[j+1]); co[k]+=s[min(i+1,j+1)]; v0.push_back(v[i]); vi0.push_back(id[i]); } co[k]&=1; } for(int i=0;i<v0.size();i++){ v[i]=v0[i]; id[i]=vi0[i]; } for(int i=0;i<v1.size();i++){ v[i+v0.size()]=v1[i]; id[i+v0.size()]=vi1[i]; } } int ans=0; for(int k=0;k<30;k++){ if(co[k]){ ans^=(1<<k); } } cout<<ans<<endl; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 504 KB | Output is correct |
2 | Correct | 7 ms | 504 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1671 ms | 33896 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1671 ms | 33896 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 504 KB | Output is correct |
2 | Correct | 7 ms | 504 KB | Output is correct |
3 | Correct | 154 ms | 4968 KB | Output is correct |
4 | Correct | 158 ms | 4840 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 504 KB | Output is correct |
2 | Correct | 7 ms | 504 KB | Output is correct |
3 | Execution timed out | 1671 ms | 33896 KB | Time limit exceeded |
4 | Halted | 0 ms | 0 KB | - |