# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
730066 | 2023-04-25T08:10:57 Z | fdnfksd | XOR Sum (info1cup17_xorsum) | C++14 | 675 ms | 44456 KB |
#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
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 468 KB | Output is correct |
2 | Correct | 4 ms | 468 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 503 ms | 38400 KB | Output is correct |
2 | Correct | 480 ms | 34896 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 503 ms | 38400 KB | Output is correct |
2 | Correct | 480 ms | 34896 KB | Output is correct |
3 | Correct | 587 ms | 41712 KB | Output is correct |
4 | Correct | 519 ms | 39108 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 468 KB | Output is correct |
2 | Correct | 4 ms | 468 KB | Output is correct |
3 | Correct | 62 ms | 4752 KB | Output is correct |
4 | Correct | 61 ms | 4836 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 468 KB | Output is correct |
2 | Correct | 4 ms | 468 KB | Output is correct |
3 | Correct | 503 ms | 38400 KB | Output is correct |
4 | Correct | 480 ms | 34896 KB | Output is correct |
5 | Correct | 587 ms | 41712 KB | Output is correct |
6 | Correct | 519 ms | 39108 KB | Output is correct |
7 | Correct | 62 ms | 4752 KB | Output is correct |
8 | Correct | 61 ms | 4836 KB | Output is correct |
9 | Correct | 675 ms | 44172 KB | Output is correct |
10 | Correct | 642 ms | 44456 KB | Output is correct |
11 | Correct | 633 ms | 44196 KB | Output is correct |