Submission #7808434


Source Code Expand

Copy
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import numpy as np
from numpy.fft import rfft,irfft

N = int(readline())
AB = np.array(read().split(),np.int32)

A = AB[::2]; B = AB[1::2]

fft_len = 2*10**5

x = irfft(rfft(A,fft_len) * rfft(B,fft_len))

print(0)
print('\n'.join((x[:N+N-1]+.5).astype(int).astype(str)))

Submission Info

Submission Time
Task C - 高速フーリエ変換
User maspy
Language Python (3.4.3)
Score 100
Code Size 437 Byte
Status AC
Exec Time 311 ms
Memory 61616 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 1
AC × 33
Set Name Test Cases
Sample 00_sample_01
All 00_sample_01, 01_00_01, 01_01_19, 01_02_31, 01_03_22, 01_04_31, 01_05_40, 01_06_15, 01_07_39, 01_08_28, 01_09_30, 01_10_23, 01_11_33, 01_12_11, 01_13_28, 01_14_41, 01_15_26, 01_16_49, 01_17_34, 01_18_02, 01_19_33, 01_20_29, 02_00_51254, 02_01_82431, 02_02_17056, 02_03_34866, 02_04_6779, 02_05_65534, 02_06_65535, 02_07_65536, 02_08_65537, 02_09_65538, 02_10_100000
Case Name Status Exec Time Memory
00_sample_01 AC 181 ms 22632 KB
01_00_01 AC 167 ms 22724 KB
01_01_19 AC 168 ms 21808 KB
01_02_31 AC 168 ms 22832 KB
01_03_22 AC 166 ms 23236 KB
01_04_31 AC 166 ms 21808 KB
01_05_40 AC 168 ms 21808 KB
01_06_15 AC 169 ms 22448 KB
01_07_39 AC 168 ms 22704 KB
01_08_28 AC 167 ms 21844 KB
01_09_30 AC 167 ms 22512 KB
01_10_23 AC 168 ms 22576 KB
01_11_33 AC 168 ms 22832 KB
01_12_11 AC 168 ms 22488 KB
01_13_28 AC 167 ms 21828 KB
01_14_41 AC 167 ms 21808 KB
01_15_26 AC 168 ms 22960 KB
01_16_49 AC 168 ms 21808 KB
01_17_34 AC 169 ms 22232 KB
01_18_02 AC 168 ms 21808 KB
01_19_33 AC 168 ms 22960 KB
01_20_29 AC 168 ms 22468 KB
02_00_51254 AC 240 ms 39544 KB
02_01_82431 AC 284 ms 53680 KB
02_02_17056 AC 190 ms 24452 KB
02_03_34866 AC 221 ms 32228 KB
02_04_6779 AC 177 ms 22864 KB
02_05_65534 AC 258 ms 46040 KB
02_06_65535 AC 259 ms 46084 KB
02_07_65536 AC 265 ms 46040 KB
02_08_65537 AC 260 ms 46020 KB
02_09_65538 AC 259 ms 45984 KB
02_10_100000 AC 311 ms 61616 KB