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:
def main():
    class rolling_hash():
        def __init__(self, seq):
            seq_size = len(seq)  # 文字列の長さ
            self.H0s = [0]*(seq_size+1)  # 先頭からi-1文字目までのハッシュ値
            H0s, p = self.H0s, 0
            for i, j in enumerate(seq):
                p = (p+(j+1)*pow(3, i, mod)) % mod
                H0s[i+1] = p

        def calc_hash(self, l, r):  # l文字目からr-1文字目までのハッシュ値
            H0s = self.H0s
            return ((H0s[r]-H0s[l])*pow(3, l*(mod-2), mod)) % mod

    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    mod = 2**61-1

    memo = [0]*n

    for k in range(32):
        a1 = [i % 2 for i in a]
        a1 += a1
        a2 = [i ^ 1 for i in a1]
        b_hash = rolling_hash([i % 2 for i in b]).calc_hash(0, n)
        a1 = rolling_hash(a1)
        a2 = rolling_hash(a2)
        for i, j in enumerate(memo):
            if j is None:
                continue
            elif a1.calc_hash(i, i+n) == b_hash:
                pass
            elif a2.calc_hash(i, i+n) == b_hash:
                memo[i] += 2**k
            else:
                memo[i] = None
        a = [i // 2 for i in a]
        b = [i // 2 for i in b]

    for i, j in enumerate(memo):
        if j is not None:
            print(i, j)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    class rolling_hash():
        def __init__(self, sequence):
            seq_size = len(sequence)  # 文字列の長さ
            self.Hash_0start = [0]*(seq_size+1)  # 先頭からi-1文字目までのハッシュ値
            p = 0
            for i, j in enumerate(sequence):
                p = (p+(j+1)*pow(3, i, mod)) % mod
                self.Hash_0start[i+1] = p

        def calc_hash(self, l, r):  # l文字目からr-1文字目までのハッシュ値
            return ((self.Hash_0start[r] - self.Hash_0start[l])
                    * pow(3, l*(mod-2), mod)) % mod

    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    mod = 2**61-1

    memo = [0]*n

    for k in range(32):
        a1 = [i % 2 for i in a]
        a1 += a1
        a2 = [i ^ 1 for i in a1]
        b_hash = rolling_hash([i % 2 for i in b]).calc_hash(0, n)
        a1 = rolling_hash(a1)
        a2 = rolling_hash(a2)
        for i, j in enumerate(memo):
            if j is None:
                continue
            elif a1.calc_hash(i, i+n) == b_hash:
                pass
            elif a2.calc_hash(i, i+n) == b_hash:
                memo[i] += 2**k
            else:
                memo[i] = None
        a = [i // 2 for i in a]
        b = [i // 2 for i in b]

    for i, j in enumerate(memo):
        if j is not None:
            print(i, j)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    class rolling_hash():
        def __init__(self, sequence):
            seq_size = len(sequence)  # 文字列の長さ
            self.Hash_0start = [0]*(seq_size+1)  # 先頭からi-1文字目までのハッシュ値
            for i, j in enumerate(sequence):
                self.Hash_0start[i+1] = self.Hash_0start[i] + \
                    (j+1)*pow(3, i, mod)

        def calc_hash(self, l, r):  # l文字目からr-1文字目までのハッシュ値
            return ((self.Hash_0start[r] - self.Hash_0start[l])
                    * pow(3, l*(mod-2), mod)) % mod

    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    mod = 2**61-1

    memo = [0]*n

    for k in range(32):
        a1 = [i % 2 for i in a]
        a1 += a1
        a2 = [i ^ 1 for i in a1]
        b_hash = rolling_hash([i % 2 for i in b]).calc_hash(0, n)
        a1 = rolling_hash(a1)
        a2 = rolling_hash(a2)
        for i, j in enumerate(memo):
            if j is None:
                continue
            elif a1.calc_hash(i, i+n) == b_hash:
                pass
            elif a2.calc_hash(i, i+n) == b_hash:
                memo[i] += 2**k
            else:
                memo[i] = None
        a = [i // 2 for i in a]
        b = [i // 2 for i in b]

    for i, j in enumerate(memo):
        if j is not None:
            print(i, j)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    class rolling_hash():
        def __init__(self, sequence, char_list=None):
            self.sequence = sequence  # 文字列
            self.seq_size = len(self.sequence)  # 文字列の長さ
            self.mod = 2**61-1  # mod
            if char_list is None:  # 使われている文字のリスト
                self.char_list = 'abcdefghijklmnopqrstuvwxyz'
            else:
                self.char_list = char_list
            self.base = len(self.char_list)+1  # 文字の種類数
            self.char_dict = {j: i+1 for i,
                              j in enumerate(self.char_list)}  # 文字と数値の対応表
            self.Hash_0start = [0]*(self.seq_size+1)  # 先頭からi-1文字目までのハッシュ値
            for i in range(self.seq_size):
                self.Hash_0start[i+1] = self.Hash_0start[i] + \
                    self.char_dict[self.sequence[i]] * \
                    pow(self.base, i, self.mod)

        def calc_hash(self, l, r):  # l文字目からr-1文字目までのハッシュ値
            return ((self.Hash_0start[r] - self.Hash_0start[l])
                    * pow(self.base, l*(self.mod-2), self.mod)) % self.mod

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

    memo = [0]*n

    for k in range(32):
        a1 = [i % 2 for i in a]
        a1 += a1
        a2 = [i ^ 1 for i in a1]
        b_hash = rolling_hash([i % 2 for i in b], [0, 1]).calc_hash(0, n)
        a1 = rolling_hash(a1, [0, 1])
        a2 = rolling_hash(a2, [0, 1])
        for i in range(n):
            if memo[i] is None:
                continue
            elif a1.calc_hash(i, i+n) == b_hash:
                pass
            elif a2.calc_hash(i, i+n) == b_hash:
                memo[i] += 2**k
            else:
                memo[i] = None
        a = [i // 2 for i in a]
        b = [i // 2 for i in b]

    for i, j in enumerate(memo):
        if j != None:
            print(i, j)


main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# import time
import sys
from collections import Counter, defaultdict
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))

gpw = None


class RH():
    def __init__(self, s, base, mod):
        self.base = base
        self.mod = mod

        l = len(s)
        self.h = h = [0]*(l+1)
        tmp = 0
        for i in range(l):
            tmp = (tmp*base + s[i]) % mod
            h[i+1] = tmp

        global gpw
        if gpw is None:
            self.pw = pw = [1]*(len(s)+1)
            v = 1
            for i in range(l):
                pw[i+1] = v = v * base % mod
            gpw = pw
        else:
            self.pw = gpw

    def calc(self, l, r):
        return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod


def slv(N, A, B):
    L = max(max(A), max(B)).bit_length()
    ah = []
    bh = []
    bnh = []
    for i in range(L):
        ta = []
        tb = []
        tbn = []
        for a, b in zip(A, B):
            ta.append(a >> i & 1)
            tb.append(b >> i & 1)
            tbn.append(tb[-1] ^ 1)
        ah.append(RH(ta, 641, 10**9+7))
        bh.append(RH(tb, 641, 10**9+7))
        bnh.append(RH(tbn, 641, 10**9+7))

    ans = []
    for k in range(N):
        x = 0
        for i in range(L):
            l = ah[i].calc(k, N)
            r = ah[i].calc(0, k)
            if l == bnh[i].calc(0, N-k) and r == bnh[i].calc(N-k, N):
                x += 1 << i
            elif l == bh[i].calc(0, N-k) and r == bh[i].calc(N-k, N):
                pass
            else:
                break
        else:
            ans.append('%d %d' % (k, x))

    return ans


def main():
    N = read_int()
    A = read_int_n()
    B = read_int_n()
    print(*slv(N, A, B), sep='\n')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# import time
import sys
from collections import Counter, defaultdict
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline


def read_int():
    return int(buff_readline())

def read_int_n():
    return list(map(int, buff_readline().split()))

gpw = None

class RH():
    def __init__(self, s, base, mod):
        self.base = base
        self.mod = mod
        self.rev = pow(base, mod-2, mod)

        l = len(s)
        self.h = h = [0]*(l+1)
        tmp = 0
        for i in range(l):
            tmp = (tmp*base + s[i]) % mod
            h[i+1] = tmp

        global gpw
        if gpw is None:
            self.pw = pw = [1]*(len(s)+1)
            v = 1
            for i in range(l):
                pw[i+1] = v = v * base % mod
            gpw = pw
        else:
            self.pw = gpw

    def calc(self, l, r):
        return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod


def slv(N, A, B):
    L = max(max(A), max(B)).bit_length()

    ah = []
    for i in range(L):
        ta = []
        for a in A:
            ta.append(a >> i & 1)
        ah.append(RH(ta, 641, 10**9+7))

    bh = []
    bnh = []
    for i in range(L):
        tb = []
        tbn = []
        for b in B:
            tb.append(b >> i & 1)
            tbn.append(tb[-1] ^ 1)
        bh.append(RH(tb, 641, 10**9+7))
        bnh.append(RH(tbn, 641, 10**9+7))


    ans = []
    for k in range(N):
        x = 0
        for i in range(L):
            l = ah[i].calc(k, N)
            r = ah[i].calc(0, k)
            if l == bh[i].calc(0, N-k) and r == bh[i].calc(N-k, N):
                pass
            elif l == bnh[i].calc(0, N-k) and r == bnh[i].calc(N-k, N):
                x += 1 << i
            else:
                break
        else:
            ans.append('%d %d' % (k, x))

    return ans


def main():
    N = read_int()
    A = read_int_n()
    B = read_int_n()
    print(*slv(N, A, B), sep='\n')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# import time
import sys
from collections import Counter, defaultdict
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline


def read_int():
    return int(buff_readline())

def read_int_n():
    return list(map(int, buff_readline().split()))

gpw = None

class RH():
    def __init__(self, s, base, mod):
        self.base = base
        self.mod = mod
        self.rev = pow(base, mod-2, mod)

        l = len(s)
        self.h = h = [0]*(l+1)
        tmp = 0
        for i in range(l):
            tmp = (tmp*base + s[i]) % mod
            h[i+1] = tmp

        global gpw
        if gpw is None:
            self.pw = pw = [1]*(len(s)+1)
            v = 1
            for i in range(l):
                pw[i+1] = v = v * base % mod
            gpw = pw
        else:
            self.pw = gpw

    def calc(self, l, r):
        return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod


def slv(N, A, B):
    L = max(max(A), max(B)).bit_length()
    ah = []
    bh = []
    bnh = []
    for i in range(L):
        ta = []
        tb = []
        tbn = []
        for a, b in zip(A, B):
            ta.append(a >> i & 1)
            tb.append(b >> i & 1)
            tbn.append(tb[-1] ^ 1)
        ah.append(RH(ta, 641, 10**9+7))
        bh.append(RH(tb, 641, 10**9+7))
        bnh.append(RH(tbn, 641, 10**9+7))

    ans = []
    for k in range(N):
        x = 0
        for i in range(L):
            l = ah[i].calc(k, N)
            r = ah[i].calc(0, k)
            if l == bh[i].calc(0, N-k) and r == bh[i].calc(N-k, N):
                pass
            elif l == bnh[i].calc(0, N-k) and r == bnh[i].calc(N-k, N):
                x += 1 << i
            else:
                break
        else:
            ans.append('%d %d' % (k, x))

    return ans


def main():
    N = read_int()
    A = read_int_n()
    B = read_int_n()
    print(*slv(N, A, B), sep='\n')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# import time
import sys
from collections import Counter, defaultdict
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline


def read_int():
    return int(buff_readline())

def read_int_n():
    return list(map(int, buff_readline().split()))

gpw = None

class RH():
    def __init__(self, s, base, mod):
        self.base = base
        self.mod = mod
        self.rev = pow(base, mod-2, mod)

        l = len(s)
        self.h = h = [0]*(l+1)
        tmp = 0
        for i in range(l):
            tmp = (tmp*base + s[i]) % mod
            h[i+1] = tmp

        global gpw
        if gpw is None:
            self.pw = pw = [1]*(len(s)+1)
            v = 1
            for i in range(l):
                pw[i+1] = v = v * base % mod
            gpw = pw
        else:
            self.pw = gpw

    def calc(self, l, r):
        return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod


def slv(N, A, B):
    L = max(max(A), max(B)).bit_length()
    ba = []
    bb = []
    ah = []
    bh = []
    bnh = []
    for i in range(L):
        ta = []
        tb = []
        tbn = []
        for a, b in zip(A, B):
            ta.append(a >> i & 1)
            tb.append(b >> i & 1)
            tbn.append(tb[-1] ^ 1)
        ba.append(ta)
        bb.append(tb)
        ah.append(RH(ta, 641, 10**9+7))
        bh.append(RH(tb, 641, 10**9+7))
        bnh.append(RH(tbn, 641, 10**9+7))

    ans = []
    for k in range(N):
        x = 0
        for i in range(L):
            l = ah[i].calc(k, N)
            r = ah[i].calc(0, k)
            if l == bh[i].calc(0, N-k) and r == bh[i].calc(N-k, N):
                pass
            elif l == bnh[i].calc(0, N-k) and r == bnh[i].calc(N-k, N):
                x += 1 << i
            else:
                break
        else:
            ans.append('%d %d' % (k, x))

    return ans


def main():
    N = read_int()
    A = read_int_n()
    B = read_int_n()
    print(*slv(N, A, B), sep='\n')

    # import random
    # N = 2 * 10**5
    # # A = [random.randint(0, 1 << 30) for _ in range(N)]
    # # B = [random.randint(0, 1 << 30) for _ in range(N)]
    # A = [2 ** 30 for _ in range(N)]
    # B = [2 ** 30 for _ in range(N)]
    # print(N)
    # print(*A)
    # print(*B)
    # # print(*slv(N, A, B), sep='\n')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# import time
import sys
from collections import Counter, defaultdict
buff_readline = sys.stdin.readline
readline = sys.stdin.readline


def read_int_n():
    return list(map(int, buff_readline().split()))

gpw = None

class RH():
    def __init__(self, s, base, mod):
        self.base = base
        self.mod = mod
        self.rev = pow(base, mod-2, mod)

        l = len(s)
        self.h = h = [0]*(l+1)
        tmp = 0
        for i in range(l):
            tmp = (tmp*base + s[i]) % mod
            h[i+1] = tmp

        global gpw
        if gpw is None:
            self.pw = pw = [1]*(len(s)+1)
            v = 1
            for i in range(l):
                pw[i+1] = v = v * base % mod
            gpw = pw
        else:
            self.pw = gpw

    def calc(self, l, r):
        return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod


def slv(N, A, B):
    L = max(max(A), max(B)).bit_length()
    ba = []
    bb = []
    ah = []
    bh = []
    bnh = []
    for i in range(L):
        ta = []
        tb = []
        tbn = []
        for a, b in zip(A, B):
            ta.append(a >> i & 1)
            tb.append(b >> i & 1)
            tbn.append(tb[-1] ^ 1)
        ba.append(ta)
        bb.append(tb)
        ah.append(RH(ta, 641, 10**9+7))
        bh.append(RH(tb, 641, 10**9+7))
        bnh.append(RH(tbn, 641, 10**9+7))

    ans = []
    for k in range(N):
        x = 0
        for i in range(L):
            l = ah[i].calc(k, N)
            r = ah[i].calc(0, k)
            if l == bh[i].calc(0, N-k) and r == bh[i].calc(N-k, N):
                pass
            elif l == bnh[i].calc(0, N-k) and r == bnh[i].calc(N-k, N):
                x += 1 << i
            else:
                break
        else:
            ans.append('%d %d' % (k, x))

    return ans


def main():
    N = int(input())
    A = read_int_n()
    B = read_int_n()
    print(*slv(N, A, B), sep='\n')

    # import random
    # N = 2 * 10**5
    # # A = [random.randint(0, 1 << 30) for _ in range(N)]
    # # B = [random.randint(0, 1 << 30) for _ in range(N)]
    # A = [2 ** 30 for _ in range(N)]
    # B = [2 ** 30 for _ in range(N)]
    # print(N)
    # print(*A)
    # print(*B)
    # # print(*slv(N, A, B), sep='\n')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# import time
import sys
from collections import Counter, defaultdict
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline


gpw = None


class RH():
    def __init__(self, s, base, mod):
        self.base = base
        self.mod = mod
        self.rev = pow(base, mod-2, mod)

        l = len(s)
        self.h = h = [0]*(l+1)
        tmp = 0
        for i in range(l):
            tmp = (tmp*base + s[i]) % mod
            h[i+1] = tmp

        global gpw
        if gpw is None:
            self.pw = pw = [1]*(len(s)+1)
            v = 1
            for i in range(l):
                pw[i+1] = v = v * base % mod
            gpw = pw
        else:
            self.pw = gpw

    def calc(self, l, r):
        return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod


def slv(N, A, B):
    # p = []
    # p.append(time.perf_counter())
    L = max(max(A), max(B)).bit_length()
    ba = []
    bb = []
    ah = []
    bh = []
    bnh = []
    for i in range(L):
        ta = []
        tb = []
        tbn = []
        for a, b in zip(A, B):
            ta.append(a >> i & 1)
            tb.append(b >> i & 1)
            tbn.append(tb[-1] ^ 1)
        ba.append(ta)
        bb.append(tb)
        n = 1
        ah.append(RH(ta, 641, 10**9+7))
        bh.append(RH(tb, 641, 10**9+7))
        bnh.append(RH(tbn, 641, 10**9+7))

    # p.append(time.perf_counter())

    ans = []
    for k in range(N):
        x = 0
        for i in range(L):
            l = ah[i].calc(k, N)
            r = ah[i].calc(0, k)
            if l == bh[i].calc(0, N-k) and r == bh[i].calc(N-k, N):
                pass
            elif l == bnh[i].calc(0, N-k) and r == bnh[i].calc(N-k, N):
                x += 1 << i
            else:
                break
        else:
            ans.append((k, x))
    # p.append(time.perf_counter())

    # for i in range(len(p)-1):
    #     print(p[i+1]-p[i], file=sys.stderr)

    return ans


def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    for r in slv(N, A, B):
        print(*r)

    # import random
    # N = 2 * 10**5
    # # A = [random.randint(0, 1 << 30) for _ in range(N)]
    # # B = [random.randint(0, 1 << 30) for _ in range(N)]
    # A = [2 ** 30 for _ in range(N)]
    # B = [2 ** 30 for _ in range(N)]
    # print(N)
    # print(*A)
    # print(*B)
    # # print(*slv(N, A, B), sep='\n')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import Counter, defaultdict
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline


gpw = None


class RH():
    def __init__(self, s, base, mod):
        self.base = base
        self.mod = mod
        self.rev = pow(base, mod-2, mod)

        l = len(s)
        self.h = h = [0]*(l+1)
        tmp = 0
        for i in range(l):
            num = s[i]
            tmp = (tmp*base + num) % mod
            h[i+1] = tmp

        global gpw
        if gpw is None:
            self.pw = pw = [1]*(len(s)+1)
            v = 1
            for i in range(l):
                pw[i+1] = v = v * base % mod
            gpw = pw
        else:
            self.pw = gpw

    def calc(self, l, r):
        return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod


def slv(N, A, B):
    L = max(max(A), max(B)).bit_length()
    ba = []
    bb = []
    ah = []
    bh = []
    bnh = []
    for i in range(L):
        ta = []
        tb = []
        tbn = []
        for a, b in zip(A, B):
            ta.append(a >> i & 1)
            tb.append(b >> i & 1)
            tbn.append(tb[-1] ^ 1)
        ba.append(ta)
        bb.append(tb)
        n = 1
        ah.append(RH(ta, 641, 10**9+7))
        bh.append(RH(tb, 641, 10**9+7))
        bnh.append(RH(tbn, 641, 10**9+7))

    print('--', file=sys.stderr)
    ans = []
    for k in range(N):
        x = 0
        for i in range(L):
            l = ah[i].calc(k, N)
            r = ah[i].calc(0, k)
            if l == bh[i].calc(0, N-k) and r == bh[i].calc(N-k, N):
                pass
            elif l == bnh[i].calc(0, N-k) and r == bnh[i].calc(N-k, N):
                x += 1 << i
            else:
                break
        else:
            ans.append((k, x))

    return ans


def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    for r in slv(N, A, B):
        print(*r)

    # import random
    # N = 2 * 10**5
    # # A = [random.randint(0, 1 << 30) for _ in range(N)]
    # # B = [random.randint(0, 1 << 30) for _ in range(N)]
    # A = [2 ** 30 for _ in range(N)]
    # B = [2 ** 30 for _ in range(N)]
    # print(*slv(N, A, B), sep='\n')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import Counter, defaultdict
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        print(e - s, 'sec', file=sys.stderr)
        return ret

    return wrap


gpw = None

class RollingHash():
    """
    Original code is https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
    """
    class RH():
        def __init__(self, s, base, mod):
            self.base = base
            self.mod = mod
            self.rev = pow(base, mod-2, mod)

            l = len(s)
            self.h = h = [0]*(l+1)
            tmp = 0
            for i in range(l):
                num = s[i]
                tmp = (tmp*base + num) % mod
                h[i+1] = tmp

            global gpw
            if gpw is None:
                self.pw = pw = [1]*(len(s)+1)
                v = 1
                for i in range(l):
                    pw[i+1] = v = v * base % mod
                gpw = pw
            else:
                self.pw = gpw


        def calc(self, l, r):
            return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod

    @staticmethod
    def gen(a, b, num):
        result = set()
        while 1:
            import random
            import math
            random.seed()
            while 1:
                v = random.randint(a, b)//2*2+1
                if v not in result:
                    break
            for x in range(3, int(math.sqrt(v))+1, 2):
                if v % x == 0:
                    break
            else:
                result.add(v)
                if len(result) == num:
                    break
        return result

    def __init__(self, s, rand=False, num=5):
        if rand:
            bases = RollingHash.gen(2, 10**3, num)
        else:
            assert num <= 10
            bases = [641, 103, 661, 293, 547, 311, 29, 457, 613, 599][:num]

        MOD = 10**9+7
        self.rhs = [self.RH(s, b, MOD) for b in bases]

    def calc(self, l, r):
        return self.rhs[0].calc(l, r)

def slv(N, A, B):
    L = max(max(A), max(B)).bit_length()
    ba = []
    bb = []
    ah = []
    bh = []
    bnh = []
    for i in range(L):
        ta = []
        tb = []
        tbn = []
        for a, b in zip(A, B):
            ta.append(a >> i & 1)
            tb.append(b >> i & 1)
            tbn.append(tb[-1] ^ 1)
        ba.append(ta)
        bb.append(tb)
        n = 1
        ah.append(RollingHash(ta, num=n))
        bh.append(RollingHash(tb, num=n))
        bnh.append(RollingHash(tbn, num=n))

    print('--', file=sys.stderr)
    ans = []
    for k in range(N):
        x = 0
        for i in range(L):
            l = ah[i].calc(k, N)
            r = ah[i].calc(0, k)
            if l == bh[i].calc(0, N-k) and r == bh[i].calc(N-k, N):
                pass
            elif l == bnh[i].calc(0, N-k) and r == bnh[i].calc(N-k, N):
                x += 1 << i
            else:
                break
        else:
            ans.append((k, x))

    return ans



def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    for r in slv(N, A, B):
        print(*r)

    # import random
    # N = 2 * 10**5
    # # A = [random.randint(0, 1 << 30) for _ in range(N)]
    # # B = [random.randint(0, 1 << 30) for _ in range(N)]
    # A = [2 ** 30 for _ in range(N)]
    # B = [2 ** 30 for _ in range(N)]
    # print(*slv(N, A, B), sep='\n')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import Counter, defaultdict
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline


gpw = None

class RollingHash():
    """
    Original code is https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
    """
    class RH():
        def __init__(self, s, base, mod):
            self.base = base
            self.mod = mod
            self.rev = pow(base, mod-2, mod)

            l = len(s)
            self.h = h = [0]*(l+1)
            tmp = 0
            for i in range(l):
                num = s[i]
                tmp = (tmp*base + num) % mod
                h[i+1] = tmp

            global gpw
            if gpw is None:
                self.pw = pw = [1]*(len(s)+1)
                v = 1
                for i in range(l):
                    pw[i+1] = v = v * base % mod
                gpw = pw
            else:
                self.pw = gpw


        def calc(self, l, r):
            return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod

    @staticmethod
    def gen(a, b, num):
        result = set()
        while 1:
            import random
            import math
            random.seed()
            while 1:
                v = random.randint(a, b)//2*2+1
                if v not in result:
                    break
            for x in range(3, int(math.sqrt(v))+1, 2):
                if v % x == 0:
                    break
            else:
                result.add(v)
                if len(result) == num:
                    break
        return result

    def __init__(self, s, rand=False, num=5):
        if rand:
            bases = RollingHash.gen(2, 10**3, num)
        else:
            assert num <= 10
            bases = [641, 103, 661, 293, 547, 311, 29, 457, 613, 599][:num]

        MOD = 10**9+7
        self.rhs = [self.RH(s, b, MOD) for b in bases]

    def calc(self, l, r):
        return tuple(rh.calc(l, r) for rh in self.rhs)


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo


def slv(N, A, B):
    L = max(max(A), max(B)).bit_length()
    ba = []
    bb = []
    ah = []
    bh = []
    bnh = []
    for i in range(L):
        ta = []
        tb = []
        tbn = []
        for a, b in zip(A, B):
            ta.append(a >> i & 1)
            tb.append(b >> i & 1)
            tbn.append(tb[-1] ^ 1)
        ba.append(ta)
        bb.append(tb)
        n = 1
        ah.append(RollingHash(ta, num=n))
        bh.append(RollingHash(tb, num=n))
        bnh.append(RollingHash(tbn, num=n))

    ans = []
    for k in range(N):
        x = 0
        for i in range(L):
            l = ah[i].calc(k, N)
            r = ah[i].calc(0, k)
            if l == bh[i].calc(0, N-k) and r == bh[i].calc(N-k, N):
                pass
            elif l == bnh[i].calc(0, N-k) and r == bnh[i].calc(N-k, N):
                x += 1 << i
            else:
                break
        else:
            ans.append((k, x))

    return ans



def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    for r in slv(N, A, B):
        print(*r)

    # import random
    # N = 2 * 10**5
    # A = [random.randint(0, 1 << 30) for _ in range(N)]
    # B = [random.randint(0, 1 << 30) for _ in range(N)]
    # print(*slv(N, A, B), sep='\n')


if __name__ == '__main__':
    main()