Problem:
 Score : 500 points    Problem Statement You are given two integer sequences, each of length N : a_1, ..., a_N and b_1, ..., b_N .  There are N^2 ways to choose two integers i and j such that 1 \leq i, j \leq N . For each of these N^2 pairs, we will compute a_i + b_j and write it on a sheet of paper.
That is, we will write N^2 integers in total.  Compute the XOR of these N^2 integers.   Definition of XOR  The XOR of integers c_1, c_2, ..., c_m is defined as follows:   Let the XOR be X . In the binary representation of X , the digit in the 2^k 's place ( 0 \leq k ; k is an integer) is 1 if there are an odd number of integers among c_1, c_2, ...c_m whose binary representation has 1 in the 2^k 's place, and 0 if that number is even.   For example, let us compute the XOR of 3 and 5 . The binary representation of 3 is 011 , and the binary representation of 5 is 101 , thus the XOR has the binary representation 110 , that is, the XOR is 6 .

Solution (Python):

from sys import stdin
import numpy as np
ORD = 28

n = int(stdin.readline())
a = np.array(list(map(int, stdin.readline().split())))
b = np.array(list(map(int, stdin.readline().split())))

def search(a_, b_, pow2):
    c1 = np.searchsorted(a_, pow2 - b_)
    c2 = np.searchsorted(a_, 2*pow2 - b_)
    c3 = np.searchsorted(a_, 3*pow2 - b_)
    return n**2 - np.sum(c3) + np.sum(c2) - np.sum(c1)

a_ord = np.zeros((ORD, n), dtype = int)
b_ord = np.zeros((ORD, n), dtype = int)
for i in range(1, ORD+1):
    a_ord[i-1, :] = a%(2**i)
    b_ord[i-1, :] = b%(2**i)
a_ord = np.sort(a_ord, axis = 1)

ans = ''
for i in range(ORD):
    count = search(a_ord[i], b_ord[i], 2**i)
    ans += '0' if count%2 == 0 else '1'
    
count = search(a_ord[-1], b_ord[-1], 2**ORD)
ans += '0' if count%2 == 0 else '1'

print(int(ans[::-1], 2))

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
n=int(input())
A=list(map(int,input().split()))
B=list(map(int, input().split()))
ans=0
for k in range(29):
    A_k,B_k=[[],[]],[[],[]]
    for ai in A:
        A_k[(ai&(1<<k))>>k].append(ai)
    for bi in B:
        B_k[(bi&(1<<k))>>k].append(bi)
    A,B=[],[]
    for i in range(2):
        A+=A_k[i]
        B+=B_k[i]
    mod=1<<(k+1)
    A_mod=[ai%mod for ai in A]
    B_mod=[bi%mod for bi in B]
    t=1<<k
    S=[n]*4
    cnt=0
    for ai in A_mod:
        Border=[t-ai,t*2-ai,t*3-ai,t*4-ai]
        for i in range(4):
            while 0<S[i] and Border[i]<=B_mod[S[i]-1]:
                S[i]-=1            
        cnt+=((S[1]-S[0])+(S[3]-S[2]))
    if cnt&1:
        ans+=t
print(ans)

Solution (Python):

N = int(input())
A = list(map(int, input().split()))
B = sorted(list(map(int, input().split())))

from bisect import bisect_left, bisect_right
from copy import copy

ans = 0
for k in range(38):
    mod = 2**(k+1)
    T = 2**k
    A_sub = [ [], [] ]
    B_sub = [ [], [] ]
    for a in A:
        A_sub[ (a & (1<<k))>>k].append(a)
    for b in B:
        B_sub[ (b & (1<<k))>>k].append(b)

    A = sum(A_sub, [])
    B = sum(B_sub, [])

    itr = [N]*4
    count = 0
    mask = 2**(k+1)-1
    amask = [ai & mask for ai in A]
    bmask = [bi & mask for bi in B]
    for ai in amask:
        border = [
                T - ai,
                2*T - ai,
                3*T - ai,
                4*T - ai]
        for i in range(4):
            while 0 < itr[i]  and border[i] <= bmask[itr[i]-1]:
                itr[i] -= 1
        count += (itr[1] - itr[0]) + (itr[3]) - (itr[2])


    

    
    
    
    
    
    
    
    
    
    
    if not count % 2 == 0:
        ans |= 1<<k
print(ans)

Solution (Python):



N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

ans = 0
for k in range(30):
    T = 2 ** k
    A_mod = sorted([a % (2 * T) for a in A])
    B_mod = sorted([b % (2 * T) for b in B])

    tmp = 0

    r1, r2, r3 = 0, 0, 0
    for a in reversed(A_mod):
        
        
        
        while r1 < N and a + B_mod[r1] < T:
            r1 += 1
        while r2 < N and a + B_mod[r2] < 2 * T:
            r2 += 1
        while r3 < N and a + B_mod[r3] < 3 * T:
            r3 += 1

        
        tmp += (r2 - r1) + (N - r3)

    if tmp % 2 == 1:
        ans += T

print(ans)

Solution (Python):
N=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
ans=0
def f(i):
  res=0
  t=2**i
  a_nex=sorted([p%(2*t) for p in a])
  b_nex=sorted([p%(2*t) for p in b])
  l=0
  p=q=r=0
  for k in reversed(a_nex):
    while p<N and k+b_nex[p]<t:
      p+=1
    while q<N and k+b_nex[q]<2*t:
      q+=1
    while r<N and k+b_nex[r]<3*t:
      r+=1
    l+=q-p+N-r
  res=(l%2)<<i
  return res
for k in range(29):
  ans+=f(k)
print(ans)

Solution (Python):

from sys import stdin
import numpy as np


d_in = lambda: int(stdin.readline())  
ds_in = lambda: list(map(int, stdin.readline().split()))  

ORDER = 28


def np_search(b_list_, a_list_, pow2, N_):
    c1 = np.searchsorted(a_list_, pow2 - b_list_)
    c2 = np.searchsorted(a_list_, 2*pow2 - b_list_)
    c3 = np.searchsorted(a_list_, 3*pow2 - b_list_)
    return N_**2 - c3.sum() + c2.sum() - c1.sum()



N = d_in()
a_list = ds_in()
b_list = ds_in()


np_a = np.array(a_list)
np_b = np.array(b_list)
a_order_list = np.zeros((ORDER, N), dtype=int)
b_order_list = np.zeros((ORDER, N), dtype=int)
for i in range(1, ORDER+1):
    a_order_list[i-1, :] = np_a % 2**i
    b_order_list[i-1, :] = np_b % 2**i

a_order_list.sort(axis=1)

ans = ''
for i in range(ORDER):
    count = np_search(b_list_=b_order_list[i], a_list_=a_order_list[i],
            pow2=2**i, N_=N)
    if count % 2 == 1:
        ans += '1'
    else:
        ans += '0'

count = np_search(b_list_=b_order_list[-1], a_list_=a_order_list[-1],
        pow2=2**ORDER, N_=N)

if count % 2 == 1:
    ans += '1'
else:
    ans += '0'

print(int(ans[::-1], 2))

Solution (Python):
import sys

N=int(sys.stdin.readline())
A=list(map(int,sys.stdin.readline().split()))
B=list(map(int,sys.stdin.readline().split()))

ANS=""
for i in range(1,30):
    k=2**i
    XA=sorted([a%k for a in A],reverse=True)
    XB=sorted([b%k for b in B])
    XB.append(k*2)

    b0=0
    b1=0
    b2=0
    count=N*N%2

    for xa in XA:
        for j in range(b0,N+1):
            if k//2<=xa+XB[j]:
                b0=j
                break

        if b1<b0:
            b1=b0

        
        for j in range(b1,N+1):
            if xa+XB[j]>=k:
                b1=j
                break

        if b2<b1:
            b2=b1

        for j in range(b2,N+1):
            if k*3//2<=xa+XB[j]:
                b2=j
                break

        count+=b1+b0+b2

    ANS+=str(count%2)

print(int(ANS[::-1],2))

Solution (Python):
import sys

N=int(sys.stdin.readline())
A=list(map(int,sys.stdin.readline().split()))
B=list(map(int,sys.stdin.readline().split()))

ANS=""
for i in range(1,30):
    k=2**i
    XA=sorted([a%k for a in A],reverse=True)
    XB=sorted([b%k for b in B])
    XB.append(k*2)

    b0=0
    b1=0
    b2=0
    count=N*N%2

    for xa in XA:
        for j in range(b0,N+1):
            if k//2<=xa+XB[j]:
                b0=j
                break

        if b1<b0:
            b1=b0

        
        for j in range(b1,N+1):
            if xa+XB[j]>=k:
                b1=j
                break

        if b2<b1:
            b2=b1

        for j in range(b2,N+1):
            if k*3//2<=xa+XB[j]:
                b2=j
                break

        count+=b1-b0-b2

    ANS+=str(count%2)

print(int(ANS[::-1],2))

Solution (Python):
import sys

N=int(sys.stdin.readline())
A=list(map(int,sys.stdin.readline().split()))
B=list(map(int,sys.stdin.readline().split()))

ANS=""
for i in range(1,30):
    k=2**i
    XA=sorted([a%k for a in A],reverse=True)
    XB=sorted([b%k for b in B])
    XB.append(k*2)

    b0=0
    b1=0
    b2=0
    count=0

    for xa in XA:
        for j in range(b0,N+1):
            if k//2<=xa+XB[j]:
                b0=j
                break

        if b1<b0:
            b1=b0

        
        for j in range(b1,N+1):
            if xa+XB[j]>=k:
                b1=j
                break

        if b2<b1:
            b2=b1

        for j in range(b2,N+1):
            if k*3//2<=xa+XB[j]:
                b2=j
                break

        count+=(b1-b0+N-b2)

    ANS+=str(count%2)

print(int(ANS[::-1],2))

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

def count_kth_bit(k):
    ret = 0
    t = 2**k
    am = list(sorted([a%(2*t) for a in A]))
    bm = list(sorted([b%(2*t) for b in B]))

    r1 = r2 = r3 = 0
    for a in reversed(am):
        while r1 < N and a + bm[r1] < t:
            r1 += 1
        while r2 < N and a + bm[r2] < 2*t:
            r2 += 1
        while r3 < N and a + bm[r3] < 3*t:
            r3 += 1
        ret += (r2-r1) + (N-r3)
    return ret

ans = 0
for k in range(29):
    c = count_kth_bit(k)
    ans += ((c%2) << k)
print(ans)

Solution (Python):
import sys
sdin = sys.stdin.readline



n = int(sdin())
a = list(map(int, sdin().split()))
b = list(map(int, sdin().split()))

ans = 0

for k in range(29):
    
    a_nex = [[],[]]
    b_nex = [[],[]]
    for ai in a:
        a_nex[(ai & (1<<k)) >> k].append(ai)
            
    for bj in b:
        b_nex[(bj & (1<<k)) >> k].append(bj)
    

    a = []
    b = []
    for i in range(2):
        a = a + a_nex[i]
        b = b + b_nex[i]
        
    
    mask = pow(2,k+1) - 1
    a_mask = [ai & mask for ai in a]
    b_mask = [bj & mask for bj in b]
    
    
    base = pow(2,k)
    itr = [n]*4
    count = 0
    for ai in a_mask:
        border = [
                base - ai,
                2*base - ai,
                3*base - ai,
                4*base - ai
        ]
        
        for i in range(4):
            while 0 < itr[i] and border[i] <= b_mask[itr[i] - 1]:
                itr[i] -= 1
            
            
        count += ((itr[1] - itr[0]) + (itr[3] - itr[2]))
    
    
    if count & 1:
        ans += base
    
    
print(ans)

Solution (Python):
import sys
sdin = sys.stdin.readline



n = int(sdin())
a = list(map(int, sdin().split()))
b = list(map(int, sdin().split()))

ans = 0


for k in range(29):
    a_nex = [[],[]]
    b_nex = [[],[]]
    for ai in a:
        a_nex[(ai & (1<<k)) >> k].append(ai)
            
    for bj in b:
        b_nex[(bj & (1<<k)) >> k].append(bj)
    

    a = []
    b = []
    for i in range(2):
        a = a + a_nex[i]
        b = b + b_nex[i]
        
    mask = pow(2,k+1) - 1
    a_mask = [ai & mask for ai in a]
    b_mask = [bj & mask for bj in b]
    
    base = pow(2,k)
    itr = [n]*4
    count = 0
    for ai in a_mask:
        border = [
                base - ai,
                2*base - ai,
                3*base - ai,
                4*base - ai
        ]
        
        for i in range(4):
            while 0 < itr[i] and border[i] <= b_mask[itr[i] - 1]:
                itr[i] -= 1
            
            
        count += ((itr[1] - itr[0]) + (itr[3]) - itr[2])
    
    if count & 1:
        ans += base
    
    
print(ans)