Problem:


Score : 600 points

Problem Statement

Given are two sequences a=\{a_0,\ldots,a_{N-1}\} and b=\{b_0,\ldots,b_{N-1}\} of N non-negative integers each.

Snuke will choose an integer k such that 0 \leq k < N and an integer x not less than 0, to make a new sequence of length N, a'=\{a_0',\ldots,a_{N-1}'\}, as follows:

a_i'= a_{i+k \mod N}\ XOR \ x

Find all pairs (k,x) such that a' will be equal to b.

What is \mbox{ XOR }?

The XOR of integers A and B, A \mbox{ XOR } B, is defined as follows:

When A \mbox{ XOR } B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if either A or B, but not both, has 1 in the 2^k's place, and 0 otherwise.

For example, 3 \mbox{ XOR } 5 = 6. (In base two: 011 \mbox{ XOR } 101 = 110.)

Constraints

1 \leq N \leq 2 \times 10^5

0 \leq a_i,b_i < 2^{30}

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
a_0 a_1 ... a_{N-1}
b_0 b_1 ... b_{N-1}

Output

Print all pairs (k, x) such that a' and b will be equal, using one line for each pair, in ascending order of k (ascending order of x for pairs with the same k).

If there are no such pairs, the output should be empty.

Sample Input 1

3
0 2 1
1 2 3

Sample Output 1

1 3

If (k,x)=(1,3),

a_0'=(a_1\ XOR \ 3)=1

a_1'=(a_2\ XOR \ 3)=2

a_2'=(a_0\ XOR \ 3)=3

and we have a' = b.

Sample Input 2

5
0 0 0 0 0
2 2 2 2 2

Sample Output 2

0 2
1 2
2 2
3 2
4 2

Sample Input 3

6
0 1 3 7 6 4
1 5 4 6 2 3

Sample Output 3

2 2
5 5

Sample Input 4

2
1 2
0 0

Sample Output 4

No pairs may satisfy the condition.



Sample input:
3
0 2 1
1 2 3


Sample output:
1 3

Submission status: Time Limit Exceeded

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

for k in range(N):
    x=A[(k)%N]^B[0]
    for i in range(1,N):
        if x!=A[(i+k)%N]^B[i]:
            break
    else:
        print(k,x)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
'''
print(a)
print(b)
'''
a.append(a[0]);b.append(b[0])
da=[a[i]^a[i+1] for i in range(N)]*2
db=[b[i]^b[i+1] for i in range(N)]
'''
print(da)
print(db)
'''
for k in range(N):
    f=True
    for i in range(N):    
        if db[i]!=da[k+i]:
            f=False
            break
    if f:
        print(k,a[k]^b[0])

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n, *lst = map(int, read().split())
al = lst[:n]
bl = lst[n:]


def convert(A):
    return [x ^ y for x, y in zip(A, A[1:])] + [A[-1] ^ A[0]]


a = convert(al)
b = convert(bl)
alal, aa = al + al, a + a


def p_arr(p):
    n = len(p)
    arr = [0] * n
    arr[0] = -1
    k, j = -1, 0
    while j < n - 1:
        if k == -1 or p[j] == p[k]:
            j += 1
            k += 1
            arr[j] = k
        else:
            k = arr[k]
    return arr


def kmp(s, p):
    slen, plen = len(s), len(p)
    i, j = 0, 0
    arr = p_arr(p)
    lst = []
    while i < slen - 1 and j < plen:
        if j == -1 or s[i] == p[j]:
            i += 1
            j += 1
        else:
            j = arr[j]
        if j == plen:
            lst.append(i - j)
            i -= j
            j = -1
    return lst


K = kmp(aa, b)
X = [al[k] ^ bl[0] for k in K]
print('\n'.join('{} {}'.format(k, x) for k, x in zip(K, X)))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

a = [int(n) for n in input().split()]
b = [int(n) for n in input().split()]

a_diff = [a[i] ^ a[(i + 1) % N] for i in range(N)]
b_diff = [b[i] ^ b[(i + 1) % N] for i in range(N)]

a_st = ''.join(['{:030b}|'.format(n) for n in a_diff])
b_st = ''.join(['{:030b}|'.format(n) for n in b_diff])

a_st = a_st + a_st 

#print(a_st.find(b_st))
pos = a_st.find(b_st)
while pos != -1 and pos // 31 != N:
    print(pos // 31, a[pos // 31] ^ b[0])
    pos = a_st.find(b_st, pos + 1)

#print(a_st)
#print(b_st)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
*a, = map(int, input().split())
*b, = map(int, input().split())

a_bits = [0] * (30 + 1)
for _a in a:
    for j in range(30 + 1):
        if _a & (1 << j) > 0:
            a_bits[j] += 1

b_bits = [0] * (30 + 1)
for _b in b:
    for j in range(30 + 1):
        if _b & (1 << j) > 0:
            b_bits[j] += 1

counter = [0] * (2 * 10 ** 5 + 1)
for _bb in b_bits:
    counter[_bb] += 1

for k in range(n):
    x = b[0] ^ a[k]
    c = [0] * (2 * 10 ** 5 + 1)
    flg = False
    for j in range(30 + 1):
        if x & (1 << j) > 0:
            t = n - a_bits[j]
        else:
            t = a_bits[j]
        if c[t] < counter[t]:
            c[t] += 1
        else:
            flg = True
            break
    if flg:
        continue

    for _a, _b in zip(a[k:n], b):
        if _a ^ x != _b:
            flg = True
            break
    if flg:
        continue

    for _a, _b in zip(a[:k], b[n - k:]):
        if _a ^ x != _b:
            flg = True
            break
    if flg:
        continue

    print(k, x)

# aのk個手前の要素 ^ x = b

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
*a, = map(int, input().split())
*b, = map(int, input().split())

a_bits = [0] * (30 + 1)
for _a in a:
    for j in range(30 + 1):
        if _a & (1 << j) > 0:
            a_bits[j] += 1

b_bits = [0] * (30 + 1)
for _b in b:
    for j in range(30 + 1):
        if _b & (1 << j) > 0:
            b_bits[j] += 1

counter = [0] * (2 * 10 ** 5 + 1)
for _bb in b_bits:
    counter[_bb] += 1

for k in range(n):
    x = b[0] ^ a[k]
    c = [0] * (2 * 10 ** 5 + 1)
    flg = False
    for j in range(30 + 1):
        if x & (1 << j) > 0:
            t = n - a_bits[j]
        else:
            t = a_bits[j]
        if c[t] < counter[t]:
            c[t] += 1
        else:
            flg = True
            break
    if flg:
        continue

    if any(_a ^ x != b[i] for i, _a in enumerate(a[k + 1:n], 1)):
        continue

    if any(_a ^ x != b[i] for i, _a in enumerate(a[:k], n - k)):
        continue

    print(k, x)

# aのk個手前の要素 ^ x = b

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
*a, = map(int, input().split())
*b, = map(int, input().split())

a_bits = [0] * (30 + 1)
for _a in a:
    for j in range(30 + 1):
        if _a & (1 << j) > 0:
            a_bits[j] += 1

b_bits = [0] * (30 + 1)
for _b in b:
    for j in range(30 + 1):
        if _b & (1 << j) > 0:
            b_bits[j] += 1

tb = tuple(sorted(b_bits))

for k in range(n):
    x = b[0] ^ a[k]
    c = [0] * (30 + 1)
    for j in range(30 + 1):
        if x & (1 << j) > 0:
            c[j] = n - a_bits[j]
        else:
            c[j] = a_bits[j]

    if tuple(sorted(c)) != tb:
        continue

    if any(_a ^ x != b[i] for i, _a in enumerate(a[k + 1:n], 1)):
        continue

    if any(_a ^ x != b[i] for i, _a in enumerate(a[:k], n - k)):
        continue

    print(k, x)

# aのk個手前の要素 ^ x = b

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
*a, = map(int, input().split())
*b, = map(int, input().split())

a_bits = [0] * (30 + 1)
for _a in a:
    for j in range(30 + 1):
        if _a & (1 << j) > 0:
            a_bits[j] += 1

b_bits = [0] * (30 + 1)
for _b in b:
    for j in range(30 + 1):
        if _b & (1 << j) > 0:
            b_bits[j] += 1

tb = tuple(sorted(b_bits))

for k in range(n):
    x = b[0] ^ a[k]
    c = [0] * (30 + 1)
    for j in range(30 + 1):
        if x & (1 << j) > 0:
            c[j] = n - a_bits[j]
        else:
            c[j] = a_bits[j]

    if tuple(sorted(c)) != tb:
        continue

    if any(_a ^ x != b[i] for i, _a in enumerate(a[k + 1:n], 1)):
        continue

    if any(_a ^ x != b[i] for i, _a in enumerate(a[:k], n - k)):
        continue

    print(k, x)

# aのk個手前の要素 ^ x = b
# 必要条件でしか絞っていない

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

a_30 = [0]*30
b_30 = [0]*30
n_1 = 0
for i in range(n):
    n_1 += 1 << i
    for j in range(30):
        a_30[j] +=  (a[i] & 2**j) >> j << i
        b_30[j] +=  (b[i] & 2**j) >> j << i



for k in range(n):
    x = 0
    check=True
    for j in range(30):
        a_temp  = a_30[j]
        a_30[j] = (a_temp >> 1) + ((a_temp & 1) << (n-1))
        if( (a_temp ^ b_30[j]) == n_1 ):
            x += (1 << j)
        elif( a_temp ^ b_30[j] != 0 ):
            check=False
    if(check):
        print('{} {}'.format(k, x))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

a_30 = [0]*30
b_30 = [0]*30
for i in range(n):
    for j in range(30):
        a_30[j] +=  (a[i] & 2**j) >> j << i
        b_30[j] +=  (b[i] & 2**j) >> j << i


for k in range(n):
    x = 0
    check=True
    for j in range(30):
        a_temp  = a_30[j]
        a_30[j] = (a_temp >> 1) + ((a_temp & 1) << (n-1))
        if( (a_temp ^ b_30[j]) == 2**n -1 ):
            x += (1 << j)
        elif( a_temp ^ b_30[j] != 0 ):
            check=False
    if(check):
        print('{} {}'.format(k, x))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
readline = sys.stdin.readline
write = sys.stdout.write

def main():
  N = int(readline())
  a = np.array(list(map(int, readline().split())))
  b = np.array(list(map(int, readline().split())))
  NA = np.arange(N)
  
  for k in range(N):
    r = np.bitwise_xor(a[(NA+k)%N], b)
    if np.all(r == r[0]):
      print(k, r[0])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline

def main():
  N = int(readline())
  a = list(map(int, readline().split()))
  b = list(map(int, readline().split()))
  buf = []
  
  for k in range(N):
    last = None
    for i in range(N):
      r = a[(i+k)%N] ^ b[i]
      if last is not None and last != r:
      	break
      last = r
    else:
      buf.append((k, last))
  for d in buf:
    print(d[0], d[1])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline
N = int(readline())
a = list(map(int, readline().split()))
b = list(map(int, readline().split()))
 
buf = []
for k in range(N):
    c = []
    for i in range(len(a)):
      c.append(a[(i+k)%N] ^ b[i])
    for g in c:
      if(g != c[0]):
        break
    else:
      buf.append((k, c[0]))
for d in buf:
  print d[0], d[1]

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.buffer.readline
N = int(readline())
a = list(map(int, readline().split()))
b = list(map(int, readline().split()))
 
buf = []
for k in range(N):
    c = []
    for i in range(len(a)):
      c.append(a[(i+k)%N] ^ b[i])
    for g in c:
      if(g != c[0]):
        break
    else:
      buf.append((k, c[0]))
for d in buf:
  print(*d)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

buf = []
for k in range(N):
    c = []
    for i in range(len(a)):
      c.append(a[(i+k)%N] ^ b[i])
    for g in c:
      if(g != c[0]):
        break
    else:
      buf.append((k, c[0]))
for d in buf:
  print(*d)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n, *lst = map(int, read().split())


def convert(A):
    return [x ^ y for x, y in zip(A, A[1:])] + [A[-1] ^ A[0]]


al = lst[:n]
bl = lst[n:]
a = convert(al)
b = convert(bl)

alal, aa = al + al, a + a
k = 0
klst = []
while k < n:
    i = 0
    while i < n and aa[k + i] == b[i]:
        i += 1
    if not i:
        k += 1
        continue
    if i == n:
        klst.append(k)
        k += 1
    else:
        k += i

for i in klst:
    print(i, al[i] ^ bl[0])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
read = sys.stdin.buffer.read
n, *lst = map(int, read().split())

def convert(A):
    return [x ^ y for x, y in zip(A, A[1:])] + [A[-1] ^ A[0]]


al = lst[:n]
bl = lst[n:]
a = convert(al)
b = convert(bl)

alal, aa = al + al, a + a
k = 0
klst = []
while k < n:
    i = 0
    while i < n and aa[k + i] == b[i]:
        i += 1
    if i == n:
        klst.append(k)
        k += 1
    elif not i:
        k += 1
    else:
        k += i

for i in klst:
    print(i, al[i] ^ bl[0])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
read = sys.stdin.buffer.read
n, *lst = map(int, read().split())

def convert(A):
    return [x ^ y for x, y in zip(A, A[1:])] + [A[-1] ^ A[0]]


al = lst[:n]
bl = lst[n:]
a = convert(al)
b = convert(bl)

alal, aa = al + al, a + a
k = 0
klst = []
while k < n:
    i = 0
    while i < n and aa[k + i] == b[i]:
        i += 1
    if i == n:
        klst.append(k)
    k += 1
for i in klst:
    print(i, al[i] ^ bl[0])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
read = sys.stdin.buffer.read
n, *lst = map(int, read().split())

def convert(A):
    return [x ^ y for x, y in zip(A, A[1:])] + [A[-1] ^ A[0]]


al = lst[:n]
bl = lst[n:]
a = convert(al)
b = convert(bl)

alal, aa = al + al, a + a
k = 0
while k < n:
    i = 0
    while i < n and aa[k + i] == b[i]:
        i += 1
    if i == n:
        x = alal[k] ^ bl[0]
        print(k, x)
    k += 1

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
read = sys.stdin.buffer.read
n, *lst = map(int, read().split())

def convert(A):
    return [x ^ y for x, y in zip(A, A[1:])] + [A[-1] ^ A[0]]


al = lst[:n]
bl = lst[n:]
a = convert(al)
b = convert(bl)
if Counter(a)!=Counter(b):
  quit()
alal, aa = al + al, a + a
for k in range(n):
    tmp = aa[k:n + k]
    for i, j in zip(tmp, b):
        if i != j:
            break
    else:
        x = alal[k] ^ bl[0]
        print(k, x)

Submission status: Time Limit Exceeded

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

C = [a1^a2 for a1, a2 in zip(A, A[1:])] + [A[0]^A[-1]]
D = [b1^b2 for b1, b2 in zip(B, B[1:])] + [B[0]^B[-1]]

K = []
k = 0
while k < N:
  next_k = k
  is_first = True
  for i in range(N):
    if i > 0 and is_first and C[(k+i)%N] == D[0]:
      next_k = k + i
      is_first = False
    if C[(k+i)%N] != D[i]:
      if next_k == k:
        k = k + i + 1
      else:
        k = next_k
      break
  
  if i == N-1:
    K.append(k)
    if next_k == k:
      break
    else:
      k = next_k

for k in K:
  print(k, A[k]^B[0])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
read = sys.stdin.buffer.read
n, *lst = map(int, read().split())

def convert(A):
    return [x ^ y for x, y in zip(A, A[1:])] + [A[-1] ^ A[0]]


al = lst[:n]
bl = lst[n:]
a = convert(al)
b = convert(bl)
if Counter(a)!=Counter(b):
  quit()
alal, aa = al + al, a + a
for k in range(n):
    tmp = aa[k:n + k]
    if tmp == b:
        x = alal[k] ^ bl[0]
        print(k, x)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
from collections import deque
n, *lst = map(int, read().split())

def convert(A):
    return [x ^ y for x, y in zip(A, A[1:])] + [A[-1] ^ A[0]]


al = lst[:n]
bl = lst[n:]
a = convert(al)
b = convert(bl)

alal, aa = al + al, a + a
for k in range(n):
    tmp = aa[k:n + k]
    if tmp == b:
        x = alal[k] ^ bl[0]
        print(k, x)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
from collections import deque
n, *lst = map(int, read().split())

def convert(A):
    return [x ^ y for x, y in zip(A, A[1:])] + [A[-1] ^ A[0]]

al = lst[:n]
bl = lst[n:]
a = convert(al)
b = convert(bl)
for k in range(n):
    if a == b:
        x = al[0] ^ bl[0]
        print(k, x)
    al, a = al[1:] + [al[0]], a[1:] + [a[0]]

Submission status: Time Limit Exceeded

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

C = [a1^a2 for a1, a2 in zip(A, A[1:])] + [A[0]^A[-1]]
D = [b1^b2 for b1, b2 in zip(B, B[1:])] + [B[0]^B[-1]]

K = []
k = 0
while k < N:
  next_k = k
  is_first = True
  for i in range(N):
    if is_first and C[(k+i)%N] == D[0]:
      next_k = k + i
      is_first = False
    if C[(k+i)%N] != D[i]:
      break
  
  if i == N-1:
    K.append(k)
  
  k = max(k+1, next_k)

for k in K:
  print(k, A[k]^B[0])

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
from collections import deque
n, *lst = map(int, read().split())
a = deque(lst[:n])
b = lst[n:]
for k in range(n):
    tmp = a[0] ^ b[0]
    for ai, bi in zip(a, b):
        if ai ^ bi != tmp:
            break
    else:
        print(k, tmp)
    a.rotate(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
from collections import deque
n, *lst = map(int, read().split())
a = deque(lst[:n])
b = lst[n:]
for k in range(n):
    tmp = set(ai ^ bi for ai, bi in zip(a, b))
    l_tmp = len(tmp)
    if l_tmp == 1:
        print(k, tmp.pop())
    a.rotate(-1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

t = list(set(a))
k = list(set(b))
if len(t) == 1 and len(k) == 1:
  x = a[0] ^ b[0]
  for i in range(N):
    print(i, x)
  exit()

M = min(N, 30)
V = [i * N // M % N for i in range(M)]
D = [[0] * N for _ in range(M)]

for i in range(M):
  for j in range(N):
    D[i][j] = a[i] ^ b[j]

L = []
for i in range(N):
  for j in range(1, M):
    if D[0][i] != D[j][(i + j) % N]:
      break
  else:
    if i == 0:
      L.append(0)
    else:
      L.append(N - i)

L.sort()
for i in L:
  for j in range(N):
    t = a[i] ^ b[0]
    if a[(j + i) % N] ^ b[j] != t:
      break
  else:
    print(i, t)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

t = list(set(a))
k = list(set(b))
if len(t) == 1 and len(k) == 1:
  x = a[0] ^ b[0]
  for i in range(N):
    print(i, x)
  exit()

M = min(N, 50)
D = [[0] * N for _ in range(M)]

for i in range(M):
  for j in range(N):
    D[i][j] = a[i] ^ b[j]

L = []
for i in range(N):
  for j in range(1, M):
    if D[0][i] != D[j][(i + j) % N]:
      break
  else:
    if i == 0:
      L.append(0)
    else:
      L.append(N - i)

L.sort()
for i in L:
  for j in range(N):
    t = a[i] ^ b[0]
    if a[(j + i) % N] ^ b[j] != t:
      break
  else:
    print(i, t)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

t = list(set(a))
k = list(set(b))
if len(t) == 1 and len(k) == 1:
  x = a[0] ^ b[0]
  for i in range(N):
    print(i, x)
  exit()

M = min(N, 10)
D = [[0] * N for _ in range(M)]

for i in range(M):
  for j in range(N):
    D[i][j] = a[i] ^ b[j]

L = []
for i in range(N):
  for j in range(1, M):
    if D[0][i] != D[j][(i + j) % N]:
      break
  else:
    if i == 0:
      L.append(0)
    else:
      L.append(N - i)

L.sort()
for i in L:
  for j in range(N):
    t = a[i] ^ b[0]
    if a[(j + i) % N] ^ b[j] != t:
      break
  else:
    print(i, t)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

for k in range(n):
  if all(a[(i + k) % n] ^ b[i] == a[(i + k + 1) % n] ^ b[i + 1] for i in range(n - 1)):
    print(k, a[k] ^ b[0])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

t = list(set(a))
k = list(set(b))
if len(t) == 1 and len(k) == 1:
  x = a[0] ^ b[0]
  for i in range(N):
    print(i, x)
  exit()

D = [[0] * N for _ in range(2)]

for i in range(2):
  for j in range(N):
    D[i][j] = a[i] ^ b[j]

L = []
for i in range(N):
  if D[0][i] == D[1][(i + 1) % N]:
    if i == 0:
      L.append(0)
    else:
      L.append(N - i)

L.sort()
for i in L:
  for j in range(N):
    t = a[i] ^ b[0]
    if a[(j + i) % N] ^ b[j] != t:
      break
  else:
    print(i, t)