oj.uz

Submission #1086414

# Submission time Handle Problem Language Result Execution time Memory
1086414 2024-09-10T14:37:24 Z shikgom2 씽크스몰 (kriii3_TT) PyPy 3
20 / 30
 1139 ms 164296 KB 
import sys
input = sys.stdin.readline
import cmath
import math

def fft(a, inv):
    n = len(a)
    j = 0
    for i in range(1, n):
        bit = n >> 1
        while j >= bit:
            j -= bit
            bit >>= 1
        j += bit
        if i < j:
            a[i], a[j] = a[j], a[i]
    
    angle = -2 * math.pi if inv else 2 * math.pi
    length = 2
    while length <= n:
        w = [cmath.exp(angle / length * i * 1j) for i in range(length // 2)]
        for i in range(0, n, length):
            for j in range(length // 2):
                u = a[i + j]
                v = a[i + j + length // 2] * w[j]
                a[i + j] = u + v
                a[i + j + length // 2] = u - v
        length <<= 1

    if inv:
        for i in range(n):
            a[i] /= n

def multiply(a, b):
    fa = [complex(x) for x in a]
    fb = [complex(x) for x in b]
    n = 1
    while n < max(len(a), len(b)):
        n <<= 1
    fa += [0] * (n - len(fa))
    fb += [0] * (n - len(fb))

    fft(fa, False)
    fft(fb, False)
    fa = [x * y for x, y in zip(fa, fb)]
    fft(fa, True)
    return [int(x.real + (0.5 if x.real > 0 else -0.5)) for x in fa]

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

n += 1
m += 1
k = 1
while k < 2 * max(n, m) - 1:
    k <<= 1
a += [0] * (k - len(a))
b += [0] * (k - len(b))

res = multiply(a, b)
ans = 0
for x in res[:n + m - 1]:
    ans ^= x
print(ans)

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 18228 KB Output is correct
2 Correct 29 ms 18200 KB Output is correct
3 Correct 33 ms 19000 KB Output is correct
4 Correct 63 ms 21648 KB Output is correct
5 Correct 50 ms 21304 KB Output is correct
6 Correct 52 ms 21040 KB Output is correct
7 Correct 54 ms 21256 KB Output is correct
8 Correct 49 ms 21296 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 36676 KB Output is correct
2 Correct 532 ms 98932 KB Output is correct
3 Correct 493 ms 96636 KB Output is correct
4 Correct 535 ms 94568 KB Output is correct
5 Correct 583 ms 97600 KB Output is correct
6 Correct 544 ms 100320 KB Output is correct
7 Correct 553 ms 101628 KB Output is correct
8 Correct 562 ms 101168 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1139 ms 164296 KB Output isn't correct
2 Halted 0 ms 0 KB -