結果

問題 No.2581 [Cherry Anniversary 3] 28輪の桜のブーケ
ユーザー LyricalMaestroLyricalMaestro
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 92 ms
76,464 KB
testcase_01 AC 87 ms
76,568 KB
testcase_02 AC 125 ms
77,064 KB
testcase_03 AC 419 ms
77,580 KB
testcase_04 AC 250 ms
77,056 KB
testcase_05 AC 117 ms
76,856 KB
testcase_06 AC 327 ms
76,744 KB
testcase_07 AC 314 ms
77,524 KB
testcase_08 AC 170 ms
77,396 KB
testcase_09 AC 267 ms
77,796 KB
testcase_10 AC 318 ms
77,052 KB
testcase_11 AC 161 ms
77,580 KB
testcase_12 AC 378 ms
76,988 KB
testcase_13 AC 451 ms
77,720 KB
testcase_14 AC 392 ms
77,372 KB
testcase_15 AC 424 ms
77,796 KB
testcase_16 AC 386 ms
77,408 KB
testcase_17 AC 434 ms
77,756 KB
testcase_18 AC 415 ms
76,848 KB
testcase_19 AC 464 ms
77,928 KB
testcase_20 AC 437 ms
77,252 KB
testcase_21 AC 438 ms
76,920 KB
testcase_22 AC 892 ms
77,312 KB
testcase_23 AC 919 ms
76,912 KB
testcase_24 AC 915 ms
77,224 KB
testcase_25 AC 866 ms
76,892 KB
testcase_26 AC 876 ms
76,720 KB
testcase_27 AC 58 ms
74,236 KB
testcase_28 AC 69 ms
76,004 KB
testcase_29 AC 822 ms
77,620 KB
testcase_30 AC 264 ms
76,984 KB
testcase_31 AC 442 ms
78,232 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