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: Wrong Answer

Solution code:
# F
#import sys
#input = sys.stdin.readline
import numpy as np
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

diffs = []
for lis in [a, b]:
    lis_tmp = np.array(lis[1:]+[lis[0]])
    diffs.append(list(abs(lis_tmp-np.array(lis))))

ad = diffs[0]
bd = (diffs[1]*2)[:-1]

ans_set = []
find_str = ad[0]
start_pos = 0
Searching = True
try:
    find_ind = bd[start_pos:].index(find_str)+start_pos
except:
    Searching = False
while(Searching and find_ind < N):
    bd_tmp=bd[find_ind:find_ind+N]
    
    
    """    Check_Same=True
    for i in range(N):
        if not ad[i]==bd_tmp[i]:
            Check_Same=False
            break"""
    if np.count_nonzero(np.array(ad)-np.array(bd_tmp))==0:
        k = N-find_ind
        x = abs(b[find_ind]-a[0])
        ans_set.append([k % N, x])
    start_pos = find_ind+1
    if start_pos >= N:
        break
    try:
        find_ind = bd[start_pos:].index(find_str)+start_pos
    except:
        break

ans_set = sorted(ans_set, key=lambda x: (x[0], x[1]))

for k, x in ans_set:
    print(k, x)

Submission status: Wrong Answer

Solution code:
# F
#import sys
#input = sys.stdin.readline
import numpy as np
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

diffs = []
for lis in [a, b]:
    lis_tmp=np.array(lis[1:]+[lis[0]])
    lis_diff=list(abs(lis_tmp-np.array(lis)))
    diffs.append(lis_diff)

str_a_diff = " ".join(map(str, diffs[0]))
str_b_diff = " ".join(map(str, diffs[1]+diffs[1][:-1]))


start_pos = 0
ans_set = []
A_Including = True
try:
    ind_a = str_b_diff[start_pos:].find(str_a_diff)+start_pos
except:
    A_Including = False

while(A_Including and ind_a >= start_pos):
    ind_diff = str_b_diff[:ind_a].count(" ")
    k = N-ind_diff
    x = abs(b[ind_diff]-a[0])
    ans_set.append([k%N, x])
    start_pos = ind_a+2
    try:
        ind_a = str_b_diff[start_pos:].find(str_a_diff)+start_pos
    except:
        A_Including = False

ans_set=sorted(ans_set, key=lambda x:x[1])        
ans_set=sorted(ans_set, key=lambda x:x[0])        

for k, x in ans_set:
    print(k, x)

Submission status: Wrong Answer

Solution code:
# F
#import sys
#input = sys.stdin.readline
import numpy as np
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

diffs = []
for lis in [a, b]:
    lis_tmp=np.array(lis[1:]+[lis[0]])
    lis_diff=list(abs(lis_tmp-np.array(lis)))
    diffs.append(lis_diff)

str_a_diff = " ".join(map(str, diffs[0]))
str_b_diff = " ".join(map(str, diffs[1]+diffs[1][:-1]))


start_pos = 0
ans_set = []
A_Including = True
try:
    ind_a = str_b_diff[start_pos:].find(str_a_diff)+start_pos
except:
    A_Including = False

while(A_Including and ind_a >= start_pos):
    ind_diff = str_b_diff[:ind_a].count(" ")
    k = N-ind_diff
    x = abs(b[ind_diff]-a[0])
    ans_set.append([k, x])
    start_pos = ind_a+2
    try:
        ind_a = str_b_diff[start_pos:].find(str_a_diff)+start_pos
    except:
        A_Including = False

ans_set=sorted(ans_set, key=lambda x:x[1])        
ans_set=sorted(ans_set, key=lambda x:x[0])        

for k, x in ans_set:
    print(k%N, x)

Submission status: Wrong Answer

Solution code:
# F
import sys
input = sys.stdin.readline
import numpy as np
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

diffs = []
for lis in [a, b]:
    lis_tmp=np.array(lis[1:]+[lis[0]])
    lis_diff=list(abs(lis_tmp-np.array(lis)))
    diffs.append(lis_diff)

str_a_diff = " ".join(map(str, diffs[0]))
str_b_diff = " ".join(map(str, diffs[1]+diffs[1][:-1]))


start_pos = 0
ans_set = []
A_Including = True
try:
    ind_a = str_b_diff[start_pos:].find(str_a_diff)+start_pos
except:
    A_Including = False

while(A_Including and ind_a >= start_pos):
    ind_diff = str_b_diff[:ind_a].count(" ")
    k = N-ind_diff
    x = abs(b[ind_diff]-a[0])
    ans_set.append([k, x])
    start_pos = ind_a+2
    try:
        ind_a = str_b_diff[start_pos:].find(str_a_diff)+start_pos
    except:
        A_Including = False

for k, x in ans_set:
    print(k%N, x)

Submission status: Wrong Answer

Solution code:
# F

N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.append(a[0])
b.append(b[0])

diffs = []
for lis in [a, b]:
    list_tmp = [str(abs(lis[ind+1]-lis[ind])) for ind in range(N)]
    diffs.append(list_tmp)

str_a_diff = " ".join(diffs[0])
str_b_diff = " ".join(diffs[1]+diffs[1][:-1])


start_pos = 0
ans_set = []
A_Including = True
try:
    ind_a = str_b_diff[start_pos:].find(str_a_diff)+start_pos
except:
    A_Including = False

while(A_Including and ind_a >= start_pos):
    ind_diff = str_b_diff[:ind_a].count(" ")
    k = N-ind_diff
    x = abs(b[ind_diff]-a[0])
    ans_set.append([k, x])
    start_pos = ind_a+2
    try:
        ind_a = str_b_diff[start_pos:].find(str_a_diff)+start_pos
    except:
        A_Including = False

for k, x in ans_set:
    print(k%N, x)

Submission status: Wrong Answer

Solution code:
# F

N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.append(a[0])
b.append(b[0])

diffs = []
for lis in [a, b]:
    list_tmp = [abs(lis[ind+1]-lis[ind]) for ind in range(N)]
    diffs.append(list(map(str, list_tmp)))

str_a_diff = " ".join(diffs[0])
str_b_diff = " ".join(diffs[1]+diffs[1][:-1])


start_pos = 0
ans_set = []
A_Including = True
try:
    ind_a = str_b_diff[start_pos:].find(str_a_diff)+start_pos
except:
    A_Including = False

while(A_Including and ind_a >= start_pos):
    ind_diff = str_b_diff[:ind_a].count(" ")
    k = N-ind_diff
    x = abs(b[ind_diff]-a[0])
    ans_set.append([k, x])
    start_pos = ind_a+2
    try:
        ind_a = str_b_diff[start_pos:].find(str_a_diff)+start_pos
    except:
        A_Including = False

for k, x in ans_set:
    print(k, x)

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
a = np.array(input().split(),dtype=int)
b = np.array(input().split(),dtype=int)

c = np.zeros(n)
d = np.zeros(n)
k = []
for i in range(n):
    c[i] = a[i]^a[(i+1)%n]
    d[i] = b[i]^b[(i+1)%n]
'''
for i in range(n):
    if c[i] == d[0]:
        flag = True
        for j in range(n):
            if not c[(i+j)%n] == d[j]:
                flag = False
                break
        if flag:
            k.append(i)
'''
for i in k:
    x = a[i]^b[0]
    print(i,x)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
A = []
B = []
ans = []
for i in range(N):
    A.append(a[i]^a[(i+1)%N])
    B.append(b[i]^b[(i+1)%N])
if A == B:
    for i in range(N):
        ans.append((i,a[i]^b[0]))
else:
    A += A    
    d = defaultdict(list)
    for i in range(N):
        d[B[i]].append(i)
    i = 0
    ans = []
    while i < N:
        ok = True
        for j in range(N):
            if B[N-j-1] != A[N-j-1+i]:
                if d[A[N-j-1]] == []:
                    i += N
                    ok = False
                    break
                else:
                    i += N - d[A[N-j-1+i]][-1] - 1
                    ok = False
                    break
        if ok:
            ans.append((i,a[i]^b[0]))
            if len(d[A[N-1+i]]) == 1:
                i += N
            else:
                i += N - d[A[N-1+i]][-2] - 1
for x in ans:
    print(*x)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
A = []
B = []
ans = []
for i in range(N):
    A.append(a[i]^a[(i+1)%N])
    B.append(b[i]^b[(i+1)%N])
for k in range(N):
    A = A[1:]+A[:1]
    if B == A:
        ans.append((k,a[k]^b[0]))
for x in ans:
    print(*x)

Submission status: Wrong Answer

Solution code:
def get_next_int():
    return int(input().rstrip("\n"))


def get_next_ints(delim=" "):
    return tuple([int(x) for x in input().rstrip("\n").split(delim)])


def main():
    n = get_next_int()

    a = get_next_ints()
    b = get_next_ints()

    a_offsets = []
    b_offsets = []
    for i in range(n):
        a_offsets.append(str(a[i] ^ a[i - 1]))
        b_offsets.append(str(b[i] ^ b[i - 1]))
    #print(a_offsets)
    #print(b_offsets)
    a_text = " ".join(a_offsets)
    b_text = " ".join(b_offsets)
    target_text = a_text + " " + a_text
    start_pos = 0
    if target_text.find(b_text, start_pos) >= 0:
        fisrt_pos = target_text.find(b_text, start_pos)
        fisrt_pos_diff = target_text[:fisrt_pos].count(" ")
        fisrt_xor_diff = b[0] ^ a[fisrt_pos_diff]
        print(fisrt_pos_diff, fisrt_xor_diff)
        if target_text.find(b_text, fisrt_pos+1) >= 0:
            second_pos = target_text.find(b_text, fisrt_pos+1)
            if second_pos < len(a):
                second_pos_diff = target_text[:second_pos].count(" ")
                second_xor_diff = b[0] ^ a[second_pos_diff]
                print(second_pos_diff, second_xor_diff)
                interval = (second_pos_diff - fisrt_pos_diff)
                remain = (n - second_pos_diff - 1) // (second_pos_diff - fisrt_pos_diff)
                for i in range(remain):
                    print(second_pos_diff + interval * (i + 1), [fisrt_xor_diff,second_xor_diff ][i % 2])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def create_table(pattern):
    table = [0 for _ in range(len(pattern))]
    j = 0
    for i in range(1, len(pattern)):
        if pattern[i] == pattern[j]:
            j += 1
            table[i] = j
        else:
            table[i] = j
            j = 0
    return table

def kmp_search(string, pattern):
    table = create_table(pattern)
    i = j = 0
    while i < len(string) and j < len(pattern):
        if string[i] == pattern[j]:
            i += 1
            j += 1
        elif j == 0:
            i += 1
        else:
            j = table[j]

    if j == len(pattern):
        return i - j
    else:
        return None


n = int(input())
a = [int(_) for _ in input().split()]
b = [int(_) for _ in input().split()]
c = ''
for i in range(n - 1):
    c += str(a[i] ^ a[i+1])
c += str(a[-1] ^ a[0])
d = ''
for i in range(n - 1):
    d += str(b[i] ^ b[i+1])
d += str(b[-1] ^ b[0])
d = d + d[:-1]

idx_list = []
idx = kmp_search(d, c)
count = 0
while idx is not None and idx != n - 1:
    idx_list.append(idx + count)
    count += idx + 1
    d = d[idx+1:]
    idx = kmp_search(d, c)
if idx is not None:
    idx_list.append(idx)

ans = []
for i in range(len(idx_list)):
    k = (n - idx_list[i]) % n
    x = a[k % n] ^ b[0]
    ans.append((k, x))

ans = sorted(ans)
for i in range(len(ans)):
    print(ans[i][0], ans[i][1])

Submission status: Wrong Answer

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

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

class RollingHash() :
    def __init__(self, S, base=26, mod=2**61-1) :
        hash = [0]
        pow = [1]
        for s in S :
            hash.append((hash[-1] * base + s) % mod)
            pow.append(pow[-1] * base % mod)

        self.hash = hash
        self.pow = pow
        self.mod = mod
        
    def get(self, l, r) :
        return (self.hash[r+1] - self.hash[l] * self.pow[r+1-l]) % self.mod

da = [a[i] ^ a[(i + 1) % N] for i in range(N)] * 2
db = [b[i] ^ b[(i + 1) % N] for i in range(N)] * 2

RHa = RollingHash(da, base=1 << 30)
RHb = RollingHash(db, base=1 << 30)

hashb = RHb.get(0, N - 1)

for i in range(N) :
  if RHa.get(i, N - 1 + i) == hashb :
    print(i, a[i] ^ b[0])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
from pprint import pprint
sys.setrecursionlimit(300000)

def make_kmp_table(word):
    m = len(word)
    ret = [0] * (m + 1)
    cur = 0
    for i in range(1, m):
        ret[i] = cur
        if word[i] == word[cur]:
            cur += 1
        else:
            cur = 0
    ret[m] = cur
    return ret

def kmp(word, doc):
    table = make_kmp_table(word)
    ret = []
    n = len(doc)
    m = len(word)
    i, p = 0, 0
    while i < n:
        if doc[i] == word[p]:
            i += 1
            p += 1
            if p == m:
                ret.append(i - m)
                p = table[m]
        elif p > 0:
            p = table[p]
        else:
            i += 1
    return ret

def solve(N: int, a: "List[int]", b: "List[int]"):
    tmp = [[-1 for _ in range(N)] for _ in range(32)]
    for i in range(32):
        a_bits = [1 if v & (1 << i) else 0 for v in a]
        b_bits = [1 if v & (1 << i) else 0 for v in b]
        s_a = sum(a_bits)
        s_b = sum(b_bits)
        if s_a == s_b:
            pos = kmp(a_bits, b_bits + b_bits)
            for p in pos:
                tmp[i][(N - p) % N] = 0
        if N - s_a == s_b:
            a_bits = [0 if v else 1 for v in a_bits]
            pos = kmp(a_bits, b_bits + b_bits)
            for p in pos:
                tmp[i][(N - p) % N] = 1

    #pprint(tmp)
    for i in range(N):
        ret = 0
        for j in range(32):
            if tmp[j][i] < 0:
                break
            else:
                ret += (2 ** j) * tmp[j][i]
        else:
            print(i, ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N - 1 - 0 + 1)]  # type: "List[int]"
    b = [int(next(tokens)) for _ in range(N - 1 - 0 + 1)]  # type: "List[int]"
    solve(N, a, b)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
from pprint import pprint
sys.setrecursionlimit(300000)

def make_kmp_table(word):
    m = len(word)
    ret = [0] * (m + 1)
    cur = 0
    for i in range(1, m):
        ret[i] = cur
        if word[i] == word[cur]:
            cur += 1
        else:
            cur = 0
    ret[m] = cur
    return ret

def kmp(word, doc):
    table = make_kmp_table(word)
    ret = []
    n = len(doc)
    m = len(word)
    i, p = 0, 0
    while i < n:
        if doc[i] == word[p]:
            i += 1
            p += 1
            if p == m:
                ret.append(i - m)
                p = table[m]
        elif p > 0:
            p = table[p]
        else:
            i += 1
    return ret

def solve(N: int, a: "List[int]", b: "List[int]"):
    tmp = [[-1 for _ in range(N)] for _ in range(32)]
    for i in range(32):
        a_bits = [(v & (1 << i)) > 0 for v in a]
        b_bits = [(v & (1 << i)) > 0 for v in b]
        pos = kmp(a_bits, b_bits + b_bits)
        for p in pos:
            tmp[i][(N - p) % N] = 0
        a_bits = [not v for v in a_bits]
        pos = kmp(a_bits, b_bits + b_bits)
        for p in pos:
            tmp[i][(N - p) % N] = 1

    #pprint(tmp)
    for i in range(N):
        ret = 0
        for j in range(32):
            if tmp[j][i] < 0:
                break
            else:
                ret += (2 ** j) * tmp[j][i]
        else:
            print(i, ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N - 1 - 0 + 1)]  # type: "List[int]"
    b = [int(next(tokens)) for _ in range(N - 1 - 0 + 1)]  # type: "List[int]"
    solve(N, a, b)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
num = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = []
d = []

for i in range(num):
    c.append(a[i] ^ a[(i+1)%num])
    d.append(b[i] ^ b[(i+1)%num])
    
c += c

# テーブル作成
table = [0]
k = 0
for i in range(1, num+1):
    table.append(k)
    if i == num:
        continue
    
    if d[i] == d[k]:
        k += 1
    else:
        k = 0

# print(table)

i = 0 # 探索される文字列の位置
j = 0 # 探索する文字列の位置
k = 0 # kの初期値
while k < num:
    while True:
        if c[i] == d[j]:
            if j == num - 1:
                print(k, a[k] ^ b[0])
                i += 1
                j = table[num]
                k = i - j
                break
            
            i += 1
            j += 1
        else:
            i += 1
            j = table[j]
            break
    
    k = i - j

Submission status: Wrong Answer

Solution code:
def xor_next(values):
    result = [0] * len(values)
    for i in range(len(values)):
        result[i] = values[i] ^ values[(i+1) % len(values)]
    return result


def make_mp_table(values):
    result = [-1] * (len(values) + 1)
    j = -1
    for i in range(len(values)):
        while j != -1 and values[j] != values[i]:
            j = result[j]
        j += 1
        result[i+1] = j
    return result


def mp_find(target, pattern, table):
    result = []
    j = 0
    for i in range(len(target)):
        while(j != -1 and pattern[j] != target[i]):
            j = table[j]
        j += 1
        if j == len(pattern):
            result.append(i-(j-1))
            j = table[j]
    return result


def main():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))

    xa = xor_next(a)
    xb = xor_next(b)
    mp_t = make_mp_table(xa)
    xb += xb
    res = mp_find(xb, xa, mp_t)
    print(res)
    res.sort(reverse=True)
    for i in range(len(res)):
        k = n-res[i]
        if(k >= n):
            continue
        x = a[k] ^ b[0]
        print(str(k) + ' ' + str(x))


main()

Submission status: Wrong Answer

Solution code:
def Z_algorithm(s):
    n = len(s)
    A = [n] + [0] * (n-1)
    i, j = 1, 0
    while i < n:
        while i + j < n and s[j] == s[i+j]:
            j += 1
        A[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < n and k + A[k] < j:
            A[i+k] = A[k]
            k += 1
        i += k
        j -= k
    return A

N = int(input())
A = [int(a) for a in input().split()]
B = [int(a) for a in input().split()]
AA = [A[i] ^ A[i-1] for i in range(N)]
BB = [B[i] ^ B[i-1] for i in range(N)]

T = Z_algorithm(AA + [-1] + BB + BB)
for i in range(N, 0, -1):
    if T[N+i] >= N:
        print(N-i, A[-i%N] ^ B[0])

Submission status: Wrong Answer

Solution code:
def Z_algorithm(s):
    n = len(s)
    A = [n] + [0] * (n-1)
    i, j = 1, 0
    while i < n:
        while i + j < n and s[j] == s[i+j]:
            j += 1
        A[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < n and k + A[k] < j:
            A[i+k] = A[k]
            k += 1
        i += k
        j -= k
    return A

N = int(input())
A = [int(a) for a in input().split()]
B = [int(a) for a in input().split()]
AA = [A[i] ^ A[i-1] for i in range(N)]
BB = [B[i] ^ B[i-1] for i in range(N)]

T = Z_algorithm(AA + BB + BB)
for i in range(N)[::-1]:
    if T[N+i] >= N:
        print(N - i, A[-i%N] ^ B[0])

Submission status: Wrong Answer

Solution code:
def Z_algorithm(s):
    n = len(s)
    A = [n] + [0] * (n-1)
    i, j = 1, 0
    while i < n:
        while i + j < n and s[j] == s[i+j]:
            j += 1
        A[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < n and k + A[k] < j:
            A[i+k] = A[k]
            k += 1
        i += k
        j -= k
    return A

N = int(input())
A = [int(a) for a in input().split()]
B = [int(a) for a in input().split()]
AA = [A[i] ^ A[i-1] for i in range(N)]
BB = [B[i] ^ B[i-1] for i in range(N)]

T = Z_algorithm(AA + BB + BB)
for i in range(N)[::-1]:
    if T[N+i] >= N:
        j = - i % N
        print(j, A[j] ^ B[0])

Submission status: Wrong Answer

Solution code:
def p_f():
    N = int(input())
    *A, = map(int, input().split())
    *B, = map(int, input().split())
    max_bit = len(bin(max(A + B))) - 2
    bit_a = []
    bit_b = []
    for i in range(max_bit):
        num = 0
        for a in A:
            num <<= 1
            num += (a >> i) & 1
        bit_a.append(num)
        num = 0
        for b in B:
            num <<= 1
            num += (b >> i) & 1
        bit_b.append(num)

    # ans = [0] * N
    # n_bit = 0
    # for a, b in zip(bit_a, bit_b):
    #     b = (b << N) + b
    #     getter = (1 << N) - 1
    #     for i in range(N):
    #         if a == ((b >> i) & getter):
    #             pass
    #         elif a == ((b >> i) & getter ^ getter):
    #             ans[i] += 1 << n_bit if ans[i] != -1 else 0
    #         else:
    #             ans[i] = -1
    #     n_bit += 1
    # 
    # for i, v in enumerate(ans):
    #     if v != -1:
    #         print(i, v)


if __name__ == '__main__':
    p_f()

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
def create_table(pattern):
    table = [0 for _ in range(len(pattern))]
    j = 0
    for i in range(1, len(pattern)):
        if pattern[i] == pattern[j]:
            j += 1
            table[i] = j
        else:
            table[i] = j
            j = 0
    return table

def kmp_search(string, pattern):
    table = create_table(pattern)
    i = j = 0
    ret=[]
    while i < len(string): #and j < len(pattern):
        if string[i] == pattern[j]:
            i += 1
            j += 1
        elif j == 0:
            i += 1
        else:
            j = table[j]
        if j == len(pattern):
            ret.append(i - j)
            j=table[j-1]
    return ret
#print(kmp_search(list('abcabc'),list('abc')))
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
a.append(a[0])
b.append(b[0])
a2=[]
b2=[]
for i in range(n):
    a2.append(a[i]^a[i+1])
    b2.append(b[i]^b[i+1])
aa=a2+a2
aa.pop(-1)
k=kmp_search(aa,b2)
exit()
ans=[]
for i in k:
    if i<n:
      ans.append([i,a[i]^b[0]])
for i in ans:
    print(*i)

Submission status: Wrong Answer

Solution code:
def create_table(pattern):
    table = [0 for _ in range(len(pattern))]
    j = 0
    for i in range(1, len(pattern)):
        if pattern[i] == pattern[j]:
            j += 1
            table[i] = j
        else:
            table[i] = j
            j = 0
    return table

def kmp_search(string, pattern):
    table = create_table(pattern)
    i = j = 0
    ret=[]
    while i < len(string): #and j < len(pattern):
        if string[i] == pattern[j]:
            i += 1
            j += 1
        elif j == 0:
            i += 1
        else:
            j = table[j]
        if j == len(pattern):
            ret.append(i - j)
            j=0
    return ret
#print(kmp_search(list('abcabc'),list('abc')))
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
a.append(a[0])
b.append(b[0])
a2=[]
b2=[]
for i in range(n):
    a2.append(a[i]^a[i+1])
    b2.append(b[i]^b[i+1])
aa=a2+a2
aa.pop(-1)
k=kmp_search(aa,b2)
ans=[]
for i in k:
    if i<n:
      ans.append([i,a[i]^b[0]])
for i in ans:
    print(*i)

Submission status: Wrong Answer

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)
'''
g=[0]
for i in range(1,N):
    f=True
    for j in range(N-i):
        if db[j]!=db[i+j]:
            f=False
            g.append(j)
            break
    if f:
        g.append(j)
# print(g)

k=0
while k<N:
    f=True
    for j in range(N):
        if db[j]!=da[k+j]:
            f=False
            k+=max(1,g[k])
            break
    if f:
        print(k,a[k]^b[0])
        k+=1

Submission status: Wrong Answer

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


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

b = 10**11+7
h = 10**7+7

H = [1]
for _ in range(N):
    H.append((H[-1]*b)%h)

allSum = 0
for i in range(N):
    allSum = (allSum + H[i]) % h

ok = [True]*N
ans = [0]*N

L = N.bit_length()
for l in range(L):
    HashA = 0
    ca = 0
    for i, a in enumerate(A):
        if (1<<l)&a:
            HashA = (HashA + H[i]) % h
            ca += 1

    HashB = 0
    cb = 0
    for i, a in enumerate(B):
        if (1<<l)&a:
            HashB = (HashB + H[i]) % h
            cb += 1
    
    for k in range(N):
        if (HashA+HashB)%h == allSum and (ca+cb)==N:
            ans[k] += (1<<l)
        elif HashA != HashB or ca != cb:
            ok[k] = False
        HashB = (HashB * b) % h
        if (1<<l)&B[-k-1]:
            HashB = (HashB + h - H[N] + 1) % h

for k in range(N):
    if ok[k]:
        print(k, ans[k])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
b = LI()
x = 0
for i in range(n):
    x ^= a[i]^b[i]

if n % 2:
    for k in range(n):
        if a[k] ^ x == b[0]:
            print(k,x)
else:
    if x != 0:
        print()
        quit()
    lst = []
    tmp = n
    while tmp % 2 == 0:
        tmp //= 2
    i = 0
    while i+tmp <= n:
        y = 0
        for j in range(tmp):
            y ^= a[i+j]
        i += tmp
        lst.append(y)
    lst.sort()
    for x in lst:
        for k in range(n):
            if a[k] ^ x == b[0]:
                print(k,x)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
b = LI()
x = 0
for i in range(n):
    x ^= a[i]^b[i]

if n % 2:
    for k in range(n):
        if a[k] ^ x == b[0]:
            print(k,x)
else:
    if x != 0:
        print()
        quit()
    lst = []
    tmp = n
    while tmp % 2 == 0:
        tmp //= 2
    i = 0
    while i+tmp <= n:
        y = 0
        for j in range(tmp):
            y ^= a[i+j]
        i += tmp
        lst.append(y)
    
    for x in lst:
        for k in range(n):
            if a[k] ^ x == b[0]:
                print(k,x)
                break

Submission status: Wrong Answer

Solution code:
N, = map(int, input().split())
As = list(map(int, input().split()))
Bs = list(map(int, input().split()))
tt = set(range(N))
K = 30
mask = (1<<N)-1
def ff(x, i):
    return ((x>>i) + (x<<(N-i)))&mask
for k in range(K):
    c, d = 0, 0
    for j, (a, b) in enumerate(zip(As, Bs)):
        c += ((a>>k)%2)<<j
        d += ((b>>k)%2)<<j

Submission status: Wrong Answer

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


def make():
    a, b = 1, 2
    while a < 10**17:
        a, b = b, a+b
        if a < 10**10:
            c = a
    return c, b


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

b, h = make()

H = [1]
for _ in range(N):
    H.append((H[-1]*b)%h)

allSum = 0
for i in range(N):
    allSum = (allSum + H[i]) % h

ok = [True]*N
ans = [0]*N

L = N.bit_length()
for l in range(L):
    HashA = 0
    for i, a in enumerate(A):
        if (1<<l)&a:
            HashA = (HashA + H[i]) % h

    HashB = 0
    for i, a in enumerate(B):
        if (1<<l)&a:
            HashB = (HashB + H[i]) % h
    
    for k in range(N):
        if (HashA+HashB)%h == allSum:
            ans[k] += (1<<l)
        elif HashA != HashB:
            ok[k] = False
        HashB = (HashB * b) % h
        if (1<<l)&B[-k-1]:
            HashB = (HashB - H[N] + 1) % h

for k in range(N):
    if ok[k]:
        print(k, ans[k])

Submission status: Wrong Answer

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

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

h = 10**11+7
b = 10**7+7

H = [1]
for _ in range(N):
    H.append((H[-1]*b)%h)

allSum = 0
for i in range(N):
    allSum = (allSum + H[i]) % h

ok = [True]*N
ans = [0]*N

L = N.bit_length()
for l in range(L):
    HashA = 0
    for i, a in enumerate(A):
        if (1<<l)&a:
            HashA = (HashA + H[i]) % h

    HashB = 0
    for i, a in enumerate(B):
        if (1<<l)&a:
            HashB = (HashB + H[i]) % h
    
    for k in range(N):
        if (HashA+HashB)%h == allSum:
            ans[k] += (1<<l)
        elif HashA != HashB:
            ok[k] = False
        HashB = (HashB * b) % h
        if (1<<l)&B[-k-1]:
            HashB = (HashB - H[N] + 1) % h

for k in range(N):
    if ok[k]:
        print(k, ans[k])

Submission status: Wrong Answer

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

def main():
	N = int(readline())
	a = np.array(list(map(int, readline().split())))
	b = np.array(list(map(int, readline().split())))
	for k in range(N):
		r = np.bitwise_xor(np.roll(a, k + 1), b)
		if len(np.unique(r)) == 1:
			print(k, r[0])

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

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, b)
    #r = np.bitwise_xor(a[(NA+k)%N], b)
    #if np.all(r == r[0]):
    #  pass
    #  #print(k, r[0])

if __name__ == '__main__':
    main()