Submission #730066

#TimeUsernameProblemLanguageResultExecution timeMemory
730066fdnfksdXOR Sum (info1cup17_xorsum)C++14
100 / 100
675 ms44456 KiB
#include<bits/stdc++.h> #define TASKNAME "codeforce" #define pb push_back #define pli pair<int,int> #define fi first #define se second #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); using namespace std; using ll=long long; const ll maxN=2e6; const ll inf=1e18; const ll mod=1e9+7; vector<ll> cc; ll n; ll a[maxN],b[maxN]; ll g(ll i,ll j) { return i&((1<<(j+1))-1); } ll get(ll j) { ll cnt=0; ll sum=0; for(ll i=1;i<=n;i++) { ll x=a[i]>>j&1; cnt+=x; cnt%=2; sum+=(cnt+x*(i)); sum%=2; } cnt=0; ll k=0; for(int i=cc.size()-1;i>=0;i--) { while(k<cc.size()&&g(cc[k],j-1)+g(cc[i],j-1)>=(1<<j)) k++; ll x=k; if(g(cc[i],j-1)*2>=(1<<j)) x++; cnt+=x; } cnt/=2; sum+=cnt; sum%=2; return sum; } void upd(ll j) { vector<ll> x,y; for(int i=0;i<cc.size();i++) { if(cc[i]>>j&1) x.pb(cc[i]); else y.pb(cc[i]); } for(int i=0;i<x.size();i++) { cc[i]=x[i]; } for(int i=x.size();i<x.size()+y.size();i++) { cc[i]=y[i-x.size()]; } } void solve() { cin >> n; cc.resize(n); for(int i=1;i<=n;i++) cin >> a[i],cc[i-1]=(a[i]); ll ans=0; for(int j=0;j<=29;j++) { ans+=get(j)<<j; upd(j); } //cout << cc.size()<<'\n'; //for(auto zz:cc) cout << zz<<' '; cout << ans; } int main() { fastio //freopen(TASKNAME".INP","r",stdin); //freopen(TASKNAME".OUT","w",stdout); solve(); }

Compilation message (stderr)

xorsum.cpp: In function 'll get(ll)':
xorsum.cpp:36:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         while(k<cc.size()&&g(cc[k],j-1)+g(cc[i],j-1)>=(1<<j)) k++;
      |               ~^~~~~~~~~~
xorsum.cpp: In function 'void upd(ll)':
xorsum.cpp:49:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(int i=0;i<cc.size();i++)
      |                 ~^~~~~~~~~~
xorsum.cpp:54:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(int i=0;i<x.size();i++)
      |                 ~^~~~~~~~~
xorsum.cpp:58:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for(int i=x.size();i<x.size()+y.size();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...