#include <bits/stdc++.h>
using namespace std;
template<typename TH>
void _dbg(const char* sdbg, TH h)
{
cerr << sdbg << " = " << h << "\n";
}
template<typename TH, typename... TA>
void _dbg(const char* sdbg, TH h, TA... t)
{
while (*sdbg != ',') cerr << *sdbg++;
cerr << " = " << h << ",";
_dbg(sdbg + 1, t...);
}
#define db(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#define chkpt cerr << "--- Checkpoint here ---\n";
const int N=1e6+6;
int n;
int64_t a[N],p10[10];
void Sub1(){
int ans=0;
for(int i=1;i<=n;++i){
for(int j=i;j<=n;++j){
ans^=(a[i]+a[j]);
}
}
cout<<ans<<'\n';
}
int GetDigit(int64_t x,int k){
return (x/p10[k-1])%10;
}
void SortByDigit(vector<int64_t> &a,int k){
vector<int> freq(10);
for(int i=0;i<a.size();++i){
freq[GetDigit(a[i],k)]++;
}
for(int i=1;i<=9;++i){
freq[i]+=freq[i-1];
}
vector<int64_t> b(a.size());
for(int i=(int)a.size()-1;i>=0;--i){
int id=GetDigit(a[i],k);
b[freq[id]-1]=a[i];
freq[id]--;
}
a=b;
}
void RadixSort(vector<int64_t> &vec){
for(int i=1;i<=9;++i){
SortByDigit(vec,i);
}
assert(is_sorted(begin(vec),end(vec)));
}
int64_t GetClass(int64_t x,int64_t m,int64_t minVal,int64_t maxVal){
if(maxVal==minVal){
return 0;
}
return (m-1)*(x-minVal)/(maxVal-minVal);
}
void FlashSort(vector<int64_t>& a){
int64_t n=a.size();
if (n>=1){
int64_t m=max((int64_t)2,(int64_t)(0.43*n));
int64_t minVal=*min_element(begin(a),end(a));
int64_t maxVal=*max_element(begin(a),end(a));
vector<int64_t> L(m,0);
L[0]=-1;
for(int i=0;i<n;++i){
L[GetClass(a[i],m,minVal,maxVal)]++;
}
for(int i=1;i<m;++i){
L[i]+=L[i-1];
}
int64_t i=0;
int64_t k=GetClass(a[0],m,minVal,maxVal);
int64_t nMove=0;
while(nMove<n){
while(i>L[k]){
i++;
k=GetClass(a[i],m,minVal,maxVal);
}
int64_t tmp=a[i];
while(i<=L[k]){
k=GetClass(tmp,m,minVal,maxVal);
swap(tmp,a[L[k]]);
L[k]--;
nMove++;
}
}
for(int k=0;k<m-1;++k){
for(int i=L[k]+2;i<=L[k+1];++i){
int64_t x=a[i],j=i;
while(j>L[k]+1&&a[j-1]>x){
a[j]=a[j-1];
j--;
}
a[j]=x;
}
}
}
assert(is_sorted(begin(a),end(a)));
}
int Check(int pos){
int res=0;
vector<vector<int64_t>> vec(2);
for(int i=1;i<=n;++i){
int64_t val=0;
for(int j=0;j<pos;++j){
if((a[i]>>j)&1){
val|=1<<j;
}
}
vec[(a[i]>>pos)&1].push_back(val);
}
FlashSort(vec[0]);
FlashSort(vec[1]);
// for(int i=0;i<2;++i){
// sort(begin(vec[i]),end(vec[i]));
// }
int ptr=(int)vec[0].size()-1;
for(int i=0;i<vec[0].size();++i){
int64_t val=(1<<pos)-vec[0][i];
while(ptr>=0&&vec[0][ptr]>=val){
ptr--;
}
if(ptr+1<=i){
res^=(i-(ptr+1)+1)%2;
}
}
ptr=(int)vec[1].size()-1;
for(int i=0;i<vec[1].size();++i){
int64_t val=(1<<pos)-vec[1][i];
while(ptr>=0&&vec[1][ptr]>=val){
ptr--;
}
if(ptr+1<=i){
res^=(i-(ptr+1)+1)%2;
}
}
ptr=(int)vec[1].size()-1;
for(int i=0;i<vec[0].size();++i){
int64_t val=(1<<pos)-vec[0][i];
while(ptr>=0&&vec[1][ptr]>=val){
ptr--;
}
res^=(ptr+1)%2;
}
return res;
}
void Sub2(){
int64_t ans=0;
for(int i=0;i<=31;++i){
if(Check(i)){
ans+=(int64_t)1<<i;
}
}
cout<<ans;
}
void Gen(){
srand(time(0));
freopen("info1cup17_xorsum.inp","w",stdout);
int n=rand()%5+1;
cout<<n<<'\n';
for(int i=1;i<=n;++i){
cout<<rand()%10+1<<' ';
}
exit(0);
}
int main()
{
// Gen();
// freopen("info1cup17_xorsum.inp","r",stdin);
// freopen("info1cup17_xorsum.out","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n;
for(int i=1;i<=n;++i){
cin>>a[i];
}
p10[0]=1;
for(int i=1;i<=9;++i){
p10[i]=p10[i-1]*10;
}
// Sub1();
Sub2();
return 0;
}
Compilation message
xorsum.cpp: In function 'void SortByDigit(std::vector<long int>&, int)':
xorsum.cpp:43:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<a.size();++i){
~^~~~~~~~~
xorsum.cpp: In function 'int Check(int)':
xorsum.cpp:134:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<vec[0].size();++i){
~^~~~~~~~~~~~~~
xorsum.cpp:144:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<vec[1].size();++i){
~^~~~~~~~~~~~~~
xorsum.cpp:154:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<vec[0].size();++i){
~^~~~~~~~~~~~~~
xorsum.cpp: In function 'void Gen()':
xorsum.cpp:176:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("info1cup17_xorsum.inp","w",stdout);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
512 KB |
Output is correct |
| 2 |
Correct |
23 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1692 ms |
25584 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1692 ms |
25584 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
512 KB |
Output is correct |
| 2 |
Correct |
23 ms |
512 KB |
Output is correct |
| 3 |
Correct |
477 ms |
3168 KB |
Output is correct |
| 4 |
Correct |
476 ms |
3344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
512 KB |
Output is correct |
| 2 |
Correct |
23 ms |
512 KB |
Output is correct |
| 3 |
Execution timed out |
1692 ms |
25584 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
