이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef pair < int , int > pp;
typedef vector < int > vi;
const int mod = 1e9 + 7;
const int N = 1e6 + 6;
pp one[N],zer[N],O[N],Z[N];
int T[N],A[N],o,z,zz,oo,n,i,j,l,x,ans;
ll t;
int main (){
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&A[i]);
if(A[i]&1) one[++o] = mp(0,i);
else zer[++z] = mp(0,i);
}
for(j=0;j<31;j++){
t = 0;
/*
for(i=1;i<=n;i++){
x = A[i];
if(x & (1<<j)){
t += o+1 - (int)(lower_bound(one+1 , one+o+1 , mp((1<<j)-T[i] , -1)) - one);
t += (int)(lower_bound(zer+1 , zer+z+1 , mp((1<<j)-T[i] , -1)) - zer-1);
}
else{
t += z+1 - (int)(lower_bound(zer+1 , zer+z+1 , mp((1<<j)-T[i] , -1)) - zer);
t += (int)(lower_bound(one+1 , one+o+1 , mp((1<<j)-T[i] , -1)) - one-1);
}
}
*/
for(l=1,i=o; i ;i--){
for(; l<=z && (1<<j)-zer[l].st > one[i].st ; l++);
t += l-1;
}
for(l=o,i=1; i<=o ;i++){
for(; l && (1<<j)-one[l].st <= one[i].st ; l--);
t += o-l;
}
for(l=z,i=1; i<=z ;i++){
for(; l && (1<<j)-zer[l].st <= zer[i].st ; l--);
t += z-l;
}
for(l=1,i=z; i ;i--){
for(; l<=o && (1<<j)-one[l].st > zer[i].st ; l++);
t += l-1;
}
for(i=1;i<=n;i++)
if((A[i]+A[i]) & (1<<j))
t++;
// if(t&1) assert(0);
t >>= 1;
if(t&1)
ans += 1 << j;
for(i=1;i<=n;i++)
T[i] += A[i] & (1 << j);
////
zz = oo = 0;
for(i=1;i<=z;i++){
l = zer[i].nd;
if(A[l] & (1<<j+1))
O[++oo] = mp(T[l],l);
else
Z[++zz] = mp(T[l],l);
}
for(i=1;i<=o;i++){
l = one[i].nd;
if(A[l] & (1<<j+1))
O[++oo] = mp(T[l],l);
else
Z[++zz] = mp(T[l],l);
}
for(i=1;i<=oo;i++) one[i]=O[i]; o = oo;
for(i=1;i<=zz;i++) zer[i]=Z[i]; z = zz;
}
printf("%d",ans);
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
xorsum.cpp: In function 'int main()':
xorsum.cpp:79:28: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
if(A[l] & (1<<j+1))
~^~
xorsum.cpp:86:28: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
if(A[l] & (1<<j+1))
~^~
xorsum.cpp:92:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for(i=1;i<=oo;i++) one[i]=O[i]; o = oo;
^~~
xorsum.cpp:92:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for(i=1;i<=oo;i++) one[i]=O[i]; o = oo;
^
xorsum.cpp:93:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for(i=1;i<=zz;i++) zer[i]=Z[i]; z = zz;
^~~
xorsum.cpp:93:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for(i=1;i<=zz;i++) zer[i]=Z[i]; z = zz;
^
xorsum.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
xorsum.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&A[i]);
~~~~~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |