# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
359136 | 2021-01-26T11:34:32 Z | ogibogi2004 | XOR Sum (info1cup17_xorsum) | C++14 | 1600 ms | 24488 KB |
#include<bits/stdc++.h> using namespace std; #define ll long long const ll MAXN=4e6+6; const ll logN=31; ll n,ans; ll a[MAXN]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n; for(ll i=1;i<=n;++i) { cin>>a[i]; } ll ans=0; for(ll j=0;j<logN;++j) { vector<ll>a1; if(j!=0) { for(ll i=1;i<=n;++i) { if(!(a[i]&(1<<(j-1)))) { a1.push_back(a[i]); } } for(ll i=1;i<=n;++i) { if(a[i]&(1<<(j-1))) { a1.push_back(a[i]); } } for(ll i=0;i<a1.size();i++)a[i+1]=a1[i]; } ll cnt0up=0,cnt1up=0,cnt0down=0,cnt1down=0; ll p=n,cnt=0; for(ll i=1;i<=n;++i) { if(a[i]&(1<<j))++cnt1up; else ++cnt0up; } for(ll i=1;i<=n;i++) { while(p>0&&a[p]%(1<<j)+a[i]%(1<<j)>=(1<<j)) { if(a[p]&(1<<j))cnt1down++,cnt1up--; else cnt0down++,cnt0up--; p--; } if(a[i]&(1<<j)) { cnt+=cnt0up+cnt1down; } else { cnt+=cnt1up+cnt0down; } if((2*a[i])&(1<<j))cnt++; } //cout<<j<<" "<<cnt<<endl; if((cnt/2)%2==1) { ans+=(1<<j); } } cout<<ans<<endl; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 492 KB | Output is correct |
2 | Correct | 7 ms | 492 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1063 ms | 24464 KB | Output is correct |
2 | Correct | 999 ms | 23564 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1063 ms | 24464 KB | Output is correct |
2 | Correct | 999 ms | 23564 KB | Output is correct |
3 | Correct | 1350 ms | 24336 KB | Output is correct |
4 | Correct | 1285 ms | 24124 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 492 KB | Output is correct |
2 | Correct | 7 ms | 492 KB | Output is correct |
3 | Correct | 176 ms | 3248 KB | Output is correct |
4 | Correct | 177 ms | 3012 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 492 KB | Output is correct |
2 | Correct | 7 ms | 492 KB | Output is correct |
3 | Correct | 1063 ms | 24464 KB | Output is correct |
4 | Correct | 999 ms | 23564 KB | Output is correct |
5 | Correct | 1350 ms | 24336 KB | Output is correct |
6 | Correct | 1285 ms | 24124 KB | Output is correct |
7 | Correct | 176 ms | 3248 KB | Output is correct |
8 | Correct | 177 ms | 3012 KB | Output is correct |
9 | Execution timed out | 1674 ms | 24488 KB | Time limit exceeded |
10 | Halted | 0 ms | 0 KB | - |