結果

問題 No.2581 [Cherry Anniversary 3] 28輪の桜のブーケ
ユーザー LyricalMaestroLyricalMaestro
提出日時 2024-01-07 04:13:04
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,017 ms / 3,000 ms
コード長 3,091 bytes
コンパイル時間 407 ms
コンパイル使用メモリ 81,572 KB
実行使用メモリ 77,956 KB
最終ジャッジ日時 2024-01-07 04:13:22
合計ジャッジ時間 16,657 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 94 ms
76,120 KB
testcase_01 AC 101 ms
76,120 KB
testcase_02 AC 141 ms
76,760 KB
testcase_03 AC 461 ms
77,288 KB
testcase_04 AC 282 ms
76,632 KB
testcase_05 AC 131 ms
76,888 KB
testcase_06 AC 378 ms
76,888 KB
testcase_07 AC 357 ms
76,888 KB
testcase_08 AC 190 ms
76,888 KB
testcase_09 AC 315 ms
77,164 KB
testcase_10 AC 351 ms
76,888 KB
testcase_11 AC 181 ms
77,288 KB
testcase_12 AC 427 ms
76,760 KB
testcase_13 AC 507 ms
77,176 KB
testcase_14 AC 430 ms
76,760 KB
testcase_15 AC 475 ms
77,260 KB
testcase_16 AC 418 ms
76,888 KB
testcase_17 AC 471 ms
77,088 KB
testcase_18 AC 455 ms
76,888 KB
testcase_19 AC 520 ms
77,260 KB
testcase_20 AC 497 ms
76,888 KB
testcase_21 AC 484 ms
76,760 KB
testcase_22 AC 1,014 ms
76,632 KB
testcase_23 AC 1,005 ms
76,504 KB
testcase_24 AC 992 ms
76,632 KB
testcase_25 AC 982 ms
76,504 KB
testcase_26 AC 1,017 ms
76,504 KB
testcase_27 AC 65 ms
72,408 KB
testcase_28 AC 75 ms
75,736 KB
testcase_29 AC 937 ms
77,272 KB
testcase_30 AC 292 ms
76,888 KB
testcase_31 AC 490 ms
77,956 KB
権限があれば一括ダウンロードができます

ソースコード

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