# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
362485 | 2021-02-03T11:04:08 Z | keta_tsimakuridze | XOR Sum (info1cup17_xorsum) | C++14 | 1600 ms | 18940 KB |
#include<bits/stdc++.h> #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],f[2][N]; vector< int > v[2]; void Sort(int i){ c[1]=c[0]=0; for(int k=1;k<=n;k++){ int b = ((1<<i)&a[pos[k]]); b=min(b,1); c[b]++; f[b][c[b]]=pos[k]; } cur=0; for(int j=0;j<=1;j++){ for(int k=1;k<=c[j];k++){ cur++; pos[cur]=f[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]] >= (1<<(i+1)) ) r--; while(l && s[pos[l]] + s[pos[k]] >= (1<<i) ) l--; cnt += r-l; cnt %=4; while( l1&&s[pos[l1]] + s[pos[k]] >=((1<<(i+1))+(1<<i)) ) l1--; cnt+=n-l1; cnt%=4; } int c1=0; for(int k=1;k<=n;k++){ if((2*a[k])&(1<<i)) c1++; } c1%=4; if((c1+(cnt-c1+4)/2)%2==1) ans+=1<<i; } cout<<ans; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 492 KB | Output is correct |
2 | Correct | 6 ms | 492 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1684 ms | 18940 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1684 ms | 18940 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 492 KB | Output is correct |
2 | Correct | 6 ms | 492 KB | Output is correct |
3 | Correct | 131 ms | 2284 KB | Output is correct |
4 | Correct | 131 ms | 2276 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 492 KB | Output is correct |
2 | Correct | 6 ms | 492 KB | Output is correct |
3 | Execution timed out | 1684 ms | 18940 KB | Time limit exceeded |
4 | Halted | 0 ms | 0 KB | - |