Submission #9392853


Source Code Expand

Copy
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# (a,b,c,d) -> (ab,bc,cd,da) と変換
# xor x で不変量になる

N = int(readline())

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

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

C = convert(A); D = convert(B)

def Z_algorithm(S):
    # 共通接頭辞の長さを返す
    N=len(S)
    arr = [0]*N
    arr[0] = N
    i,j = 1,0
    while i<N:
        while i+j<N and S[j]==S[i+j]:
            j += 1
        arr[i]=j
        if not j:
            i += 1
            continue
        k = 1
        while i+k<N and k+arr[k]<j:
            arr[i+k] = arr[k]
            k += 1
        i += k; j -= k
    return arr

Z = Z_algorithm(D + [-1] + C + C)[N+1:N+N+1]

K = [i for i,x in enumerate(Z) if x == N]
X = [A[k] ^ B[0] for k in K]

print('\n'.join('{} {}'.format(k,x) for k,x in zip(K,X)))

Submission Info

Submission Time
Task F - Xor Shift
User maspy
Language Python (3.4.3)
Score 600
Code Size 1015 Byte
Status AC
Exec Time 663 ms
Memory 67028 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 4
AC × 22
Set Name Test Cases
Sample sample_01, sample_02, sample_03, sample_04
All max_01, max_02, max_03, max_04, random_01, random_02, random_03, random_04, random_05, random_06, random_07, random_08, random_09, random_10, random_11, random_12, random_13, random_14, sample_01, sample_02, sample_03, sample_04
Case Name Status Exec Time Memory
max_01 AC 646 ms 56324 KB
max_02 AC 663 ms 67028 KB
max_03 AC 612 ms 44240 KB
max_04 AC 503 ms 41708 KB
random_01 AC 133 ms 16316 KB
random_02 AC 205 ms 26044 KB
random_03 AC 90 ms 11260 KB
random_04 AC 198 ms 25308 KB
random_05 AC 139 ms 16000 KB
random_06 AC 130 ms 15268 KB
random_07 AC 382 ms 41204 KB
random_08 AC 285 ms 31128 KB
random_09 AC 181 ms 20976 KB
random_10 AC 87 ms 10612 KB
random_11 AC 253 ms 27652 KB
random_12 AC 82 ms 9916 KB
random_13 AC 308 ms 43448 KB
random_14 AC 22 ms 3828 KB
sample_01 AC 17 ms 3064 KB
sample_02 AC 17 ms 3064 KB
sample_03 AC 17 ms 3064 KB
sample_04 AC 17 ms 3064 KB