oj.uz

Submission #1086413

# Submission time Handle Problem Language Result Execution time Memory
1086413 2024-09-10T14:27:13 Z shikgom2 씽크스몰 (kriii3_TT) PyPy 3
20 / 30
 1129 ms 167368 KB 
import sys
input = sys.stdin.readline
import cmath

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]

    length = 2
    while length <= n:
        w = [cmath.exp(2j * cmath.pi * i / length * (-1 if inv else 1)) for i in range(length >> 1)]
        for i in range(0, n, length):
            for j in range(length >> 1):
                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 30 ms 18484 KB Output is correct
2 Correct 34 ms 18240 KB Output is correct
3 Correct 36 ms 20016 KB Output is correct
4 Correct 56 ms 22060 KB Output is correct
5 Correct 55 ms 22044 KB Output is correct
6 Correct 56 ms 22096 KB Output is correct
7 Correct 55 ms 22096 KB Output is correct
8 Correct 57 ms 22068 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 36680 KB Output is correct
2 Correct 579 ms 99960 KB Output is correct
3 Correct 527 ms 100672 KB Output is correct
4 Correct 548 ms 96616 KB Output is correct
5 Correct 528 ms 97588 KB Output is correct
6 Correct 512 ms 101600 KB Output is correct
7 Correct 518 ms 101108 KB Output is correct
8 Correct 529 ms 101544 KB Output is correct

Subtask #3
0 / 10.0

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