| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 215931 | wendy_virgo | XOR Sum (info1cup17_xorsum) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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],pow10[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/pow10[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)));
}
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);
}
RadixSort(vec[0]);
RadixSort(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];
}
pow10[0]=1;
for(int i=1;i<=9;++i){
pow10[i]=pow10[i-1]*10;
}
// Sub1();
Sub2();
return 0;
}