提出 #2251624

---

ソースコード 拡げる

#include<bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector< pair<int,int> > vpii;
typedef vector< pair<ll,ll> > vpll;
typedef vector< vector<int> > matrix;

#define SET(Ar,val) memset(Ar,val,sizeof(Ar))
#define rep(i,val,n)  for(int i=val;i<n;i++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LMAX LONG_LONG_MAX
#define LMIN LONG_LONG_MIN
#define IMAX INT_MAX
#define IMIN INT_MIN
#define M 1000000007

/*--------------------------------------------------------------------------------------------------------------------------------*/

template <class T> T modpower(T a,T b,T MOD)
{
    T ans=1;
    while(b!=0)
    {
        if(b%2==1)
        ans=(ans*a)%MOD;
        a=(a*a)%MOD;
        b/=2;
    }
    return ans;
}

void init()
{
    int N,mx = -1;
    cin >> N;
    int a[N+5],b[N+5];
    rep(i,0,N)
    {
        cin >> a[i];
        mx = max(mx,a[i]);
    }
    rep(i,0,N)
    {
        cin >> b[i];
        mx = max(mx,b[i]);
    }
    int ans = 0,d, u = log(mx);
    vi a1,b1;
    rep(i,0,30)
    {
        d = (1<<(i+1));
        a1.clear();
        b1.clear();
        rep(i,0,N)
        {
            a1.pb(a[i]%d);
            b1.pb(b[i]%d);
        }
        sort(b1.begin(),b1.end());

        /*for(auto it : b1)
            cout << it << endl ;*/

        rep(j,0,N)
        {
            int v = 0;
            int id1 = lower_bound(b1.begin(),b1.end(),d/2 - a1[j]) - b1.begin();
            int id2 = upper_bound(b1.begin(),b1.end(),d - a1[j] - 1) - b1.begin() - 1;
            if(id1 < N && id2>=id1)
                v += (id2-id1+1);

            int id3 = lower_bound(b1.begin(),b1.end(),(3*(d/2)) - a1[j]) - b1.begin();
            int id4 = upper_bound(b1.begin(),b1.end(),2*d - a1[j] - 1) - b1.begin() - 1;
            if(id3 < N && id4>=id3)
                v += (id4-id3+1);

            //cout << id1 << " " << id2 << " " << id3 << " " << id4 << endl ;

            if(v%2 == 1)
                ans^=(d/2);// cout <<"asd" << ans << endl;
         }
    }
    cout << ans << endl ;
}

int main()
{
    clock_t time1=clock();
	/*#ifndef ONLINE_JUDGE
	freopen("abc_091.in","r",stdin);
	#else
	//ONLINE_JUDGE
	#endif*/
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    init();
    clock_t time2 = clock();
    cerr <<"Time: " <<(double)(time2-time1)/CLOCKS_PER_SEC <<" seconds" <<endl;
	return 0;
}

提出情報

ジャッジ結果