結果

問題 No.206 数の積集合を求めるクエリ
ユーザー かりあげクンかりあげクン
提出日時 2020-08-25 13:33:56
言語 Nim
(2.0.2)
結果
AC  
実行時間 400 ms / 7,000 ms
コード長 3,128 bytes
コンパイル時間 4,031 ms
コンパイル使用メモリ 66,328 KB
実行使用メモリ 73,480 KB
最終ジャッジ日時 2024-11-06 11:17:03
合計ジャッジ時間 15,136 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 248 ms
56,908 KB
testcase_01 AC 249 ms
57,148 KB
testcase_02 AC 252 ms
57,004 KB
testcase_03 AC 249 ms
57,028 KB
testcase_04 AC 248 ms
56,876 KB
testcase_05 AC 248 ms
56,924 KB
testcase_06 AC 244 ms
57,156 KB
testcase_07 AC 251 ms
57,168 KB
testcase_08 AC 246 ms
57,200 KB
testcase_09 AC 246 ms
57,244 KB
testcase_10 AC 247 ms
56,904 KB
testcase_11 AC 245 ms
56,960 KB
testcase_12 AC 250 ms
57,328 KB
testcase_13 AC 252 ms
57,180 KB
testcase_14 AC 323 ms
57,156 KB
testcase_15 AC 245 ms
57,056 KB
testcase_16 AC 247 ms
57,152 KB
testcase_17 AC 271 ms
69,976 KB
testcase_18 AC 257 ms
66,444 KB
testcase_19 AC 270 ms
72,328 KB
testcase_20 AC 256 ms
64,560 KB
testcase_21 AC 261 ms
65,592 KB
testcase_22 AC 260 ms
67,552 KB
testcase_23 AC 265 ms
68,440 KB
testcase_24 AC 400 ms
69,592 KB
testcase_25 AC 398 ms
73,480 KB
testcase_26 AC 381 ms
65,984 KB
testcase_27 AC 352 ms
63,128 KB
testcase_28 AC 397 ms
66,372 KB
testcase_29 AC 387 ms
65,380 KB
testcase_30 AC 383 ms
64,000 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