結果
問題 | No.206 数の積集合を求めるクエリ |
ユーザー | Navier_Boltzmann |
提出日時 | 2023-11-24 16:08:44 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 972 ms / 7,000 ms |
コード長 | 1,834 bytes |
コンパイル時間 | 372 ms |
コンパイル使用メモリ | 81,700 KB |
実行使用メモリ | 285,992 KB |
最終ジャッジ日時 | 2023-11-24 16:09:02 |
合計ジャッジ時間 | 16,183 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 48 ms
58,216 KB |
testcase_01 | AC | 49 ms
63,800 KB |
testcase_02 | AC | 66 ms
71,120 KB |
testcase_03 | AC | 47 ms
58,216 KB |
testcase_04 | AC | 50 ms
63,800 KB |
testcase_05 | AC | 58 ms
69,012 KB |
testcase_06 | AC | 90 ms
78,364 KB |
testcase_07 | AC | 90 ms
78,380 KB |
testcase_08 | AC | 91 ms
78,380 KB |
testcase_09 | AC | 91 ms
78,380 KB |
testcase_10 | AC | 46 ms
58,216 KB |
testcase_11 | AC | 69 ms
71,116 KB |
testcase_12 | AC | 100 ms
78,480 KB |
testcase_13 | AC | 97 ms
78,504 KB |
testcase_14 | AC | 102 ms
78,508 KB |
testcase_15 | AC | 97 ms
78,376 KB |
testcase_16 | AC | 97 ms
78,364 KB |
testcase_17 | AC | 952 ms
274,744 KB |
testcase_18 | AC | 971 ms
261,172 KB |
testcase_19 | AC | 917 ms
273,300 KB |
testcase_20 | AC | 944 ms
272,116 KB |
testcase_21 | AC | 972 ms
273,124 KB |
testcase_22 | AC | 953 ms
261,752 KB |
testcase_23 | AC | 956 ms
274,544 KB |
testcase_24 | AC | 966 ms
285,992 KB |
testcase_25 | AC | 954 ms
285,060 KB |
testcase_26 | AC | 906 ms
265,380 KB |
testcase_27 | AC | 925 ms
264,032 KB |
testcase_28 | AC | 898 ms
266,764 KB |
testcase_29 | AC | 945 ms
278,116 KB |
testcase_30 | AC | 919 ms
265,296 KB |
ソースコード
import cmath def convolution(f,g): n = len(bin(len(f)+len(g)-1)) - 2 fft_length = 1<<n f = f + [0]*(fft_length - len(f)) g = g + [0]*(fft_length - len(g)) def fft(a): for i in range(fft_length): j = 0 for k in range(n): j |= ((i>>k)&1) << (n - 1 - k) if i<j: a[i],a[j] = a[j],a[i] for nn in range(n): b = 1<<nn for j in range(b): w = cmath.rect(1,(-cmath.pi)*j/b) for k in range(0,fft_length,2*b): s = a[j+k] t = a[j+k+b]*w a[j+k] = s+t a[j+k+b] = s-t return a def ifft(a): for i in range(fft_length): j = 0 for k in range(n): j |= ((i>>k)&1) << (n - 1 - k) if i<j: a[i],a[j] = a[j],a[i] for nn in range(n): b = 1<<nn for j in range(b): w = cmath.rect(1,(cmath.pi)*j/b) for k in range(0,fft_length,2*b): s = a[j+k] t = a[j+k+b]*w a[j+k] = s+t a[j+k+b] = s-t return [i/fft_length for i in a] F = fft(f) G = fft(g) H = [i*j for i,j in zip(F,G)] return [round(i.real) for i in ifft(H)] from collections import * from itertools import * from functools import * from heapq import * import sys,math input = sys.stdin.readline L,M,N = map(int,input().split()) A = list(map(int,input().split())) B = list(map(int,input().split())) X = [0]*(N+1) Y = [0]*(N+1) for a in A: X[a] += 1 for b in B: Y[N-b] += 1 Q = int(input()) Z = convolution(X,Y) print(*Z[N:N+Q],sep='\n')