結果
問題 | No.1307 Rotate and Accumulate |
ユーザー | Wizist |
提出日時 | 2020-12-05 05:05:28 |
言語 | PyPy3 (7.3.13) |
結果 |
AC
|
実行時間 | 1,342 ms / 5,000 ms |
コード長 | 1,150 bytes |
コンパイル時間 | 464 ms |
コンパイル使用メモリ | 87,236 KB |
実行使用メモリ | 308,308 KB |
最終ジャッジ日時 | 2023-10-13 13:37:03 |
合計ジャッジ時間 | 13,276 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 61 ms
71,896 KB |
testcase_01 | AC | 64 ms
71,996 KB |
testcase_02 | AC | 61 ms
71,540 KB |
testcase_03 | AC | 68 ms
76,672 KB |
testcase_04 | AC | 71 ms
76,712 KB |
testcase_05 | AC | 67 ms
76,848 KB |
testcase_06 | AC | 67 ms
76,796 KB |
testcase_07 | AC | 61 ms
71,736 KB |
testcase_08 | AC | 596 ms
284,272 KB |
testcase_09 | AC | 564 ms
284,832 KB |
testcase_10 | AC | 576 ms
282,824 KB |
testcase_11 | AC | 562 ms
283,256 KB |
testcase_12 | AC | 569 ms
282,276 KB |
testcase_13 | AC | 122 ms
90,424 KB |
testcase_14 | AC | 257 ms
142,892 KB |
testcase_15 | AC | 1,227 ms
301,964 KB |
testcase_16 | AC | 1,288 ms
301,988 KB |
testcase_17 | AC | 1,249 ms
301,916 KB |
testcase_18 | AC | 1,250 ms
308,308 KB |
testcase_19 | AC | 1,262 ms
301,952 KB |
testcase_20 | AC | 1,342 ms
306,312 KB |
testcase_21 | AC | 60 ms
71,584 KB |
ソースコード
#!/usr/bin/env python3 # # No.1307 Rotate and Accumulate # import sys, os, math def fft(a, inverse=False): n = 1 while n < len(a): n <<= 1 if len(a) < n: a += [0] * (n - len(a)) j, k = 0, 1 for i in range(1, n): bit = n >> 1 while j & bit: j ^= bit; bit >>= 1 j ^= bit if i < j: a[i], a[j] = a[j], a[i] while k < n: wk = math.cos(math.pi / k) + math.sin(-math.pi / k if inverse else math.pi / k) * 1j for i in range(0, n, 2 * k): w = 1 + 0j for j in range(k): u, v = a[i + j], a[i + j + k] * w a[i + j] = u + v a[i + j + k] = u - v w *= wk k *= 2 if inverse: for i in range(n): a[i] /= n def multiply(a, b): n = 1 while n < len(a) + len(b): n <<= 1 f, g, r = [0] * n, [0] * n, [0] * n for i, v in enumerate(a): f[i] = v for i, v in enumerate(b): g[i] = v fft(f); fft(g) for i in range(n): f[i] *= g[i] fft(f, True) for i, v in enumerate(f): r[i] = round(v.real) return r def read_ints(): return list(map(int, input().split())) n, q = read_ints() a, r = read_ints(), read_ints() f = a + a g = [0] * (n + 1) for x in r: g[n - x] += 1 c = multiply(f, g) print(" ".join(map(str, c[n:n + n])))