제출 #67747

#제출 시각아이디문제언어결과실행 시간메모리
67747yusufakeXOR Sum (info1cup17_xorsum)C++98
100 / 100
1464 ms33900 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...