結果

問題 No.2581 [Cherry Anniversary 3] 28輪の桜のブーケ
ユーザー LyricalMaestro
提出日時 2024-01-07 04:13:04
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 919 ms / 3,000 ms
コード長 3,091 bytes
コンパイル時間 140 ms
コンパイル使用メモリ 82,448 KB
実行使用メモリ 78,232 KB
最終ジャッジ日時 2024-09-27 19:20:39
合計ジャッジ時間 14,216 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/2581


def main():
    M = int(input())
    G = list(map(int, input().split()))
    H = list(map(int, input().split()))
    Q = int(input())
    kx = []
    for _ in range(Q):
        kx.append(list(map(int, input().split())))

    # 半分全列挙
    N = 28
    M1 = N // 2
    M2 = N - M1
    k_map = [[] for _ in range(M1 + 1)]
    for bit in range(2 ** M1):
        someyosino_count = 0
        x = 0
        for i in range(M1):
            if bit & (1 << i) > 0:
                someyosino_count += 1
                x += G[i]
            else:
                x += H[i]
        
        x %= M
        k_map[someyosino_count].append(x)
    
    for i in range(M1 + 1):
        k_map[i].sort()

    k_map2 = [[] for _ in range(M2 + 1)]
    for bit in range(2 ** M2):
        someyosino_count = 0
        x = 0
        for i in range(M2):
            if bit & (1 << i) > 0:
                someyosino_count += 1
                x += G[M1 + i]
            else:
                x += H[M1 + i]
        
        x %= M
        k_map2[someyosino_count].append(x)

    for k0, x in kx:
        count = 0
        for k2 in range(min(M2, k0) + 1):
            k1 = k0 - k2
            if k1 > M1:
                continue
            for x2 in k_map2[k2]:
                a_flg = False
                if x2 <= x:
                    # and条件
                    a_flg = True
                    lower_x1 = x - x2
                    upper_x1 = M - 1 - x2
                else:
                    # or条件
                    lower_x1 = (x - x2) % M
                    upper_x1 = M - 1 - x2
                
                # lower_x1についての2部探索
                l_x = len(k_map[k1])
                if k_map[k1][-1] >= lower_x1:
                    low = 0
                    high = len(k_map[k1]) - 1
                    while high - low > 1:
                        mid = (low + high) // 2
                        if k_map[k1][mid] >= lower_x1:
                            high = mid
                        else:
                            low = mid
                    if k_map[k1][low] >= lower_x1:
                        l_x = low
                    else:
                        l_x = high
                u_x = -1
                if k_map[k1][0] <= upper_x1:
                    low = 0
                    high = len(k_map[k1]) - 1
                    while high - low > 1:
                        mid = (low + high) // 2
                        if k_map[k1][mid] <= upper_x1:
                            low = mid
                        else:
                            high = mid
                    if k_map[k1][high] <= upper_x1:
                        u_x = high
                    else:
                        u_x = low
                if a_flg:
                    count += u_x - l_x + 1   
                else:
                    count += len(k_map[k1]) - l_x + u_x + 1  
        
        print(count)

                
                    


        





        




if __name__ == "__main__":
    main()
0