# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
67706 | 2018-08-15T09:00:33 Z | tatatan | XOR Sum (info1cup17_xorsum) | C++11 | 1600 ms | 60776 KB |
#include <bits/stdc++.h> #define mp make_pair #define pb push_back #define pii pair<int,int> #define LL long long #define st first #define nd second #define endl '\n' using namespace std; const int MAXN=1000005; int n,a[MAXN],b[MAXN],ans; int main() { scanf("%d",&n); for(int i=0;i<n;++i) scanf("%d",&a[i]); vector<pii> v; for(int i=0;i<n;++i) v.pb(mp(0,i)); for(int i=0;i<30;++i) { int xo=(1<<(i+1))-1,t1,t2,t3; LL cnt=0; vector<pii> av,bv; for(int j=0;j<n;++j) if((1<<i)&(a[v[j].nd])) bv.pb(mp(v[j].st+(1<<i),v[j].nd)); else av.pb(v[j]); v.clear(); for(int j=0;j<av.size();++j) v.pb(av[j]); for(int j=0;j<bv.size();++j) v.pb(bv[j]); for(int j=0;j<n;++j) b[j]=v[j].st; t1=t2=t3=n; for(int j=0;j<n;++j) { while(t1&&b[t1-1]>=(1<<i)-b[j]) --t1; while(t2&&b[t2-1]>=(1<<(i+1))-b[j]) --t2; while(t3&&b[t3-1]>=(1<<(i+1))+(1<<i)-b[j]) --t3; cnt+=(n-t1-(t3-t2)); } for(int j=0;j<n;++j) if((b[j]*2)&(1<<i)) --cnt; cnt/=2; for(int j=0;j<n;++j) if((b[j]*2)&(1<<i)) ++cnt; if(cnt&1) ans+=(1<<i); } printf("%d\n",ans); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 376 KB | Output is correct |
2 | Correct | 8 ms | 484 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1264 ms | 34108 KB | Output is correct |
2 | Correct | 1322 ms | 35240 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1264 ms | 34108 KB | Output is correct |
2 | Correct | 1322 ms | 35240 KB | Output is correct |
3 | Correct | 1454 ms | 44800 KB | Output is correct |
4 | Correct | 1403 ms | 50668 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 376 KB | Output is correct |
2 | Correct | 8 ms | 484 KB | Output is correct |
3 | Correct | 170 ms | 50668 KB | Output is correct |
4 | Correct | 168 ms | 50668 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 376 KB | Output is correct |
2 | Correct | 8 ms | 484 KB | Output is correct |
3 | Correct | 1264 ms | 34108 KB | Output is correct |
4 | Correct | 1322 ms | 35240 KB | Output is correct |
5 | Correct | 1454 ms | 44800 KB | Output is correct |
6 | Correct | 1403 ms | 50668 KB | Output is correct |
7 | Correct | 170 ms | 50668 KB | Output is correct |
8 | Correct | 168 ms | 50668 KB | Output is correct |
9 | Execution timed out | 1618 ms | 60776 KB | Time limit exceeded |
10 | Halted | 0 ms | 0 KB | - |