結果
問題 | No.206 数の積集合を求めるクエリ |
ユーザー | Navier_Boltzmann |
提出日時 | 2023-07-23 02:15:14 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 642 ms / 7,000 ms |
コード長 | 1,470 bytes |
コンパイル時間 | 93 ms |
コンパイル使用メモリ | 12,060 KB |
実行使用メモリ | 71,956 KB |
最終ジャッジ日時 | 2023-10-24 08:47:34 |
合計ジャッジ時間 | 20,595 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 481 ms
42,376 KB |
testcase_01 | AC | 477 ms
42,156 KB |
testcase_02 | AC | 470 ms
42,136 KB |
testcase_03 | AC | 466 ms
42,392 KB |
testcase_04 | AC | 465 ms
42,168 KB |
testcase_05 | AC | 461 ms
42,140 KB |
testcase_06 | AC | 472 ms
42,876 KB |
testcase_07 | AC | 471 ms
42,312 KB |
testcase_08 | AC | 470 ms
42,336 KB |
testcase_09 | AC | 470 ms
42,352 KB |
testcase_10 | AC | 471 ms
42,152 KB |
testcase_11 | AC | 463 ms
42,148 KB |
testcase_12 | AC | 469 ms
43,032 KB |
testcase_13 | AC | 480 ms
42,348 KB |
testcase_14 | AC | 466 ms
42,340 KB |
testcase_15 | AC | 462 ms
42,320 KB |
testcase_16 | AC | 464 ms
42,320 KB |
testcase_17 | AC | 587 ms
71,900 KB |
testcase_18 | AC | 548 ms
66,784 KB |
testcase_19 | AC | 585 ms
70,748 KB |
testcase_20 | AC | 547 ms
66,640 KB |
testcase_21 | AC | 552 ms
69,012 KB |
testcase_22 | AC | 551 ms
68,652 KB |
testcase_23 | AC | 575 ms
71,084 KB |
testcase_24 | AC | 640 ms
71,956 KB |
testcase_25 | AC | 642 ms
68,852 KB |
testcase_26 | AC | 605 ms
66,764 KB |
testcase_27 | AC | 584 ms
66,312 KB |
testcase_28 | AC | 601 ms
67,184 KB |
testcase_29 | AC | 601 ms
68,176 KB |
testcase_30 | AC | 586 ms
64,764 KB |
ソースコード
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 import numpy as np def convolve(f, g): tf = np.array(f, np.int64) tg = np.array(g, np.int64) fft_len = 1 while 2 * fft_len < len(tf) + len(tg) - 1: fft_len *= 2 fft_len *= 2 # フーリエ変換 Ff = np.fft.rfft(tf, fft_len) Fg = np.fft.rfft(tg, fft_len) # 各点積 Fh = Ff * Fg # フーリエ逆変換 h = np.fft.irfft(Fh, fft_len) # 小数になっているので、整数にまるめる h = np.rint(h).astype(np.int64) return h[:len(f) + len(g) - 1] def convolve2(f,g,p): f1,f2 = np.divmod(f,1<<15) g1,g2 = np.divmod(g,1<<15) a = convolve(f1,g1)%p c = convolve(f2,g2)%p b = (convolve(f1+f2,g1+g2) - a - c)%p h = (a<<30) + (b<<15) + c return h%p def convolve_pow(f,n,p): nbit = list(str(bin(n))[2:]) nbit = [int(i) for i in nbit] N = len(f) C = [1] + [0]*(N-1) B = f for i in range(len(nbit)): if nbit[-1-i] == 1: C = convolve2(C,B,p) B = convolve2(B,B,p) return C Q = int(input()) Z = convolve(X,Y) print(*Z[N:N+Q],sep='\n')