# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
362480 | 2021-02-03T10:50:29 Z | keta_tsimakuridze | XOR Sum (info1cup17_xorsum) | C++14 | 1600 ms | 42196 KB |
#include<bits/stdc++.h> #define int long long #define f first #define s second using namespace std; const int N=1e6+5; int a[N],s[N],n,cnt,c[2],ans,cur,pos[N]; vector< int > v[2]; void Sort(int i){ v[0].clear(); v[1].clear(); for(int k=1;k<=n;k++){ int b = ((1ll<<i)&a[pos[k]]); b=min(b,1ll); v[b].push_back(pos[k]); } cur=0; for(int j=0;j<=1;j++){ for(int k=0;k<v[j].size();k++){ cur++; pos[cur]=v[j][k]; } } } main(){ ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>n; for(int k=1;k<=n;k++){ cin>>a[k]; pos[k]=k; cnt+=c[(a[k]&1)^1]; c[a[k]&1]++; s[k]=a[k]&1; } if(cnt%2) ans=1; Sort(0); for(int i=1;i<=30;i++){ Sort(i); for(int k=1;k<=n;k++) s[k]+=a[k]&(1ll<<i); cnt=0; int l=n,r=n,l1=n,r1=n; for(int k=1;k<=n;k++){ while(r && s[pos[r]] + s[pos[k]] >= (1ll<<(i+1)) ) r--; while(l && s[pos[l]] + s[pos[k]] >= (1ll<<i) ) l--; cnt += r-l; while( l1&&s[pos[l1]] + s[pos[k]] >=((1ll<<(i+1))+(1ll<<i)) ) l1--; cnt+=n-l1; } int c1=0; for(int k=1;k<=n;k++){ if((2*a[k])&(1ll<<i)) c1++; } if((c1+(cnt-c1)/2)%2==1) ans+=1ll<<i; } cout<<ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 492 KB | Output is correct |
2 | Correct | 5 ms | 492 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1670 ms | 42196 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1670 ms | 42196 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 492 KB | Output is correct |
2 | Correct | 5 ms | 492 KB | Output is correct |
3 | Correct | 141 ms | 4964 KB | Output is correct |
4 | Correct | 137 ms | 4836 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 492 KB | Output is correct |
2 | Correct | 5 ms | 492 KB | Output is correct |
3 | Execution timed out | 1670 ms | 42196 KB | Time limit exceeded |
4 | Halted | 0 ms | 0 KB | - |