結果

問題 No.2770 Coupon Optimization
コンテスト
ユーザー hahho
提出日時 2024-05-10 22:23:53
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,704 bytes
コンパイル時間 386 ms
コンパイル使用メモリ 81,960 KB
実行使用メモリ 266,804 KB
最終ジャッジ日時 2024-12-20 06:09:53
合計ジャッジ時間 14,124 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 2 WA * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from cmath import rect, pi


def reverse_bits32(x: int):
    x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1)
    x = ((x & 0x33333333) << 2) | ((x & 0xCCCCCCCC) >> 2)
    x = ((x & 0x0F0F0F0F) << 4) | ((x & 0xF0F0F0F0) >> 4)
    x = ((x & 0x00FF00FF) << 8) | ((x & 0xFF00FF00) >> 8)
    return ((x & 0x0000FFFF) << 16) | ((x & 0xFFFF0000) >> 16)

def fft(a, inverse=False):
    one = complex(1.0)
    n = (len(a) - 1).bit_length()
    m = 2 ** n
    a += [complex(0.0)] * (m - len(a))
    pows = [rect(1.0, (-pi if inverse else pi) / (2 ** (n - 1)))]
    for _ in range(n - 1):
        pows.append(pows[-1] ** 2)
    pows.reverse()

    shift = 32 - n
    for i in range(m):
        j = reverse_bits32(i) >> shift
        if i < j:
            a[i], a[j] = a[j], a[i]

    for i in range(m):
        b = 1
        for w1 in pows:
            if not i & b:
                break
            i ^= b
            w = one
            while not i & b:
                s = a[i]
                t = a[i | b] * w
                a[i] = s + t
                a[i | b] = s - t
                w *= w1
                i += 1
            i ^= b
            b <<= 1
    if inverse:
        c = 1 / m
        for i in range(m):
            a[i] *= c
    return a


n, m = map(int, input().split())
aa = list(map(int,input().split()))
bb = list(map(int,input().split()))

aa = [a//100 for a in aa]
bb = [100-b for b in bb]

aa.sort()
bb.sort()
if len(bb) < len(aa):
    bb += [100]*(len(aa)-len(bb))
elif len(bb) > len(aa):
    bb = bb[:len(aa)]

aa += [0]*len(aa)
bb += [0]*len(bb)
fa = fft(aa)
fb = fft(bb)
fc = [u*v for u,v in zip(fa, fb)]
cc = fft(fc, inverse=True)

for v in cc[:n]:
    print(round(v.real))
0