結果

問題 No.206 数の積集合を求めるクエリ
ユーザー かりあげクンかりあげクン
提出日時 2020-08-25 13:33:56
言語 Nim
(2.0.2)
結果
AC  
実行時間 378 ms / 7,000 ms
コード長 3,128 bytes
コンパイル時間 3,632 ms
コンパイル使用メモリ 66,176 KB
実行使用メモリ 71,296 KB
最終ジャッジ日時 2024-04-24 04:24:04
合計ジャッジ時間 13,766 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 226 ms
56,960 KB
testcase_01 AC 228 ms
56,960 KB
testcase_02 AC 228 ms
56,960 KB
testcase_03 AC 237 ms
56,960 KB
testcase_04 AC 228 ms
56,960 KB
testcase_05 AC 227 ms
56,960 KB
testcase_06 AC 225 ms
57,216 KB
testcase_07 AC 226 ms
57,216 KB
testcase_08 AC 230 ms
57,344 KB
testcase_09 AC 230 ms
57,216 KB
testcase_10 AC 226 ms
56,960 KB
testcase_11 AC 229 ms
56,960 KB
testcase_12 AC 240 ms
57,216 KB
testcase_13 AC 231 ms
57,216 KB
testcase_14 AC 231 ms
57,344 KB
testcase_15 AC 230 ms
57,088 KB
testcase_16 AC 231 ms
57,216 KB
testcase_17 AC 255 ms
67,328 KB
testcase_18 AC 240 ms
63,744 KB
testcase_19 AC 258 ms
71,296 KB
testcase_20 AC 241 ms
62,592 KB
testcase_21 AC 248 ms
64,640 KB
testcase_22 AC 250 ms
65,536 KB
testcase_23 AC 254 ms
67,200 KB
testcase_24 AC 369 ms
67,328 KB
testcase_25 AC 378 ms
71,168 KB
testcase_26 AC 353 ms
63,616 KB
testcase_27 AC 325 ms
61,696 KB
testcase_28 AC 365 ms
65,536 KB
testcase_29 AC 359 ms
64,640 KB
testcase_30 AC 360 ms
61,440 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import strutils
import sequtils
import math
import lenientops

type Complex* = tuple[re: float, im: float]
proc complex*(x: float, y: float = 0.0): Complex {.inline.} =
  (x, y)
proc `+`*(a: Complex, b: Complex): Complex {.inline.} =
  (a.re + b.re, a.im + b.im)
proc `-`*(a: Complex, b: Complex): Complex {.inline.} =
  (a.re - b.re, a.im - b.im)
proc `*`*(a: Complex, b: Complex): Complex {.inline.} =
  (a.re * b.re - a.im * b.im, a.re * b.im + a.im * b.re)
proc `/`*(a: Complex, b: Complex): Complex {.inline.} =
  ( (a.re * b.re + a.im * b.im) / (b.re * b.re + b.im * b.im),
    (a.im * b.re - a.re * b.im) / (b.re * b.re + b.im * b.im) )
proc `*`*[T](a: Complex, k: T): Complex {.inline.} =
  (a.re * k, a.im * k)
proc `/`*[T](a: Complex, k: T): Complex {.inline.} =
  (a.re / k, a.im / k)
proc inv*(a: Complex): Complex {.inline.} =
  (a.re / a.re * a.re + a.im * a.im,
  -a.im / a.re * a.re + a.im * a.im)
proc `+=`*(a: var Complex, b: Complex) {.inline.} =
  a = a + b
proc `-=`*(a: var Complex, b: Complex) {.inline.} =
  a = a - b
proc `*=`*(a: var Complex, b: Complex) {.inline.} =
  a = a * b
proc `/=`*(a: var Complex, b: Complex) {.inline.} =
  a = a / b
proc `*=`*[T](a: var Complex, k: T) {.inline.} =
  a = a * k
proc `/=`*[T](a: var Complex, k: T) {.inline.} =
  a = a / k

proc dft*(F: var seq[Complex]): seq[Complex] =
  let N = F.len
  let mask = N - 1
  var tmp = newSeq[Complex](N)
  var i = N
  while i > 1:
    i = i shr 1
    let theta = 2 * PI * i / N
    let zeta = complex(cos(theta), sin(theta))
    var powZeta = complex(1.0)
    var j = 0
    while j < N:
      for k in 0 .. i - 1:
        tmp[j + k] = F[((j shl 1) and mask) + k] + powZeta * F[(((j shl 1) + i) and mask) + k]
      powZeta *= zeta
      j += i
    swap(F, tmp)
  return F

proc idft*(F: var seq[Complex]): seq[Complex] =
  let N = F.len
  let mask = N - 1
  var tmp = newSeq[Complex](N)
  var i = N
  while i > 1:
    i = i shr 1
    let theta = -1 * 2 * PI * i / N
    let zeta = complex(cos(theta), sin(theta))
    var powZeta = complex(1.0)
    var j = 0
    while j < N:
      for k in 0 .. i - 1:
        tmp[j + k] = F[((j shl 1) and mask) + k] + powZeta * F[(((j shl 1) + i) and mask) + k]
      powZeta *= zeta
      j += i
    swap(F, tmp)
  F.applyIt(it / N.float)
  return F

proc multiply*(A: seq[Complex], B: seq[Complex]): seq[int] =
  let N = nextPowerOfTwo(A.high + B.high + 1)
  var invA = A
  invA.setLen(N)
  invA = dft(invA)
  var invB = B
  invB.setLen(N)
  invB = dft(invB)
  var invF = newSeq[Complex](N)
  for i in 0 .. N - 1:
    invF[i] = invA[i] * invB[i]
  let F = idft(invF).mapIt(int(round(it.re)))
  return F

const FFT_max : int = 1 shl 18
var
  lmn     = stdin.readLine.split.map(parseInt)
  A       = stdin.readLine.split.map(parseInt)
  B       = stdin.readLine.split.map(parseInt)
  Q       = stdin.readLine.parseInt
  (l,m,n) = (lmn[0], lmn[1], lmn[2])
  A_poly  = newSeq[Complex](FFT_max)
  B_poly  = newSeq[Complex](FFT_max)
for i in 0..<l:
  A_poly[A[i] - 1] = (1.0, 0.0)
for i in 0..<m:
  B_poly[n - B[i]] = (1.0, 0.0)

var C = multiply(A_poly, B_poly)

for i in 0..<Q:
  echo C[n-1+i]
0