結果

問題 No.2581 [Cherry Anniversary 3] 28輪の桜のブーケ
ユーザー 👑 KazunKazun
提出日時 2023-11-12 22:03:48
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,469 ms / 3,000 ms
コード長 2,974 bytes
コンパイル時間 302 ms
コンパイル使用メモリ 81,700 KB
実行使用メモリ 78,848 KB
最終ジャッジ日時 2023-12-08 23:30:22
合計ジャッジ時間 21,424 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 134 ms
77,256 KB
testcase_01 AC 133 ms
77,128 KB
testcase_02 AC 211 ms
77,640 KB
testcase_03 AC 571 ms
78,380 KB
testcase_04 AC 411 ms
77,804 KB
testcase_05 AC 200 ms
77,920 KB
testcase_06 AC 513 ms
77,752 KB
testcase_07 AC 516 ms
78,036 KB
testcase_08 AC 259 ms
77,640 KB
testcase_09 AC 382 ms
78,120 KB
testcase_10 AC 506 ms
77,836 KB
testcase_11 AC 219 ms
77,732 KB
testcase_12 AC 602 ms
78,444 KB
testcase_13 AC 653 ms
77,784 KB
testcase_14 AC 604 ms
78,656 KB
testcase_15 AC 580 ms
77,872 KB
testcase_16 AC 601 ms
78,192 KB
testcase_17 AC 598 ms
77,700 KB
testcase_18 AC 632 ms
78,508 KB
testcase_19 AC 695 ms
78,848 KB
testcase_20 AC 669 ms
77,456 KB
testcase_21 AC 679 ms
78,376 KB
testcase_22 AC 1,469 ms
77,292 KB
testcase_23 AC 1,202 ms
77,392 KB
testcase_24 AC 1,214 ms
77,656 KB
testcase_25 AC 1,190 ms
77,216 KB
testcase_26 AC 1,469 ms
77,228 KB
testcase_27 AC 72 ms
75,720 KB
testcase_28 AC 89 ms
76,104 KB
testcase_29 AC 1,117 ms
77,992 KB
testcase_30 AC 565 ms
78,404 KB
testcase_31 AC 616 ms
77,608 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

def Binary_Search_Small_Count(A, x, equal=False, sort=False):
    """二分探索によって, x 未満の要素の個数を調べる.

    A: リスト
    x: 調べる要素
    sort: ソートをする必要があるかどうか (True で必要)
    equal: True のときは x "未満" が x "以下" になる
    """
    if sort:
        A.sort()

    if len(A)==0 or A[0]>x or ((not equal) and A[0]==x):
        return 0

    L,R=0,len(A)
    while R-L>1:
        C=L+(R-L)//2
        if A[C]<x or (equal and A[C]==x):
            L=C
        else:
            R=C

    return L+1

def Binary_Search_Big_Count(A, x, equal=False, sort=False):
    """二分探索によって, x を超える要素の個数を調べる.

    A: リスト
    x: 調べる要素
    sort: ソートをする必要があるかどうか (True で必要)
    equal: True のときは x "を超える" が x "以上" になる
    """

    if sort:
        A.sort()

    if len(A)==0 or A[-1]<x or ((not equal) and A[-1]==x):
        return 0

    L,R=-1,len(A)-1
    while R-L>1:
        C=L+(R-L)//2
        if A[C]>x or (equal and A[C]==x):
            R=C
        else:
            L=C
    return len(A)-R

def Binary_Search_Range_Count(A, x, y, sort=False, left_close=True, right_close=True):
    """二分探索によって, x 以上 y 以下 の個数を調べる.

    A: リスト
    x, y: 調べる要素
    sort: ソートをする必要があるかどうか (True で必要)
    left_equal: True のときは x<=a, False のときは x<a
    right_equal: True のときは y<=a, False のときは y<a
    """

    if sort:
        A.sort()

    alpha=Binary_Search_Small_Count(A, y, equal=right_close)
    beta =Binary_Search_Small_Count(A, x, equal=not left_close)
    return max(alpha-beta,0)

def solve():
    from itertools import product

    N = 28
    M = int(input())
    G = list(map(int, input().split()))
    H = list(map(int, input().split()))

    def calc(A, B):
        n = len(A)
        res = [[] for _ in range(n + 1)]

        for P in product((0, 1), repeat = n):
            total = 0
            for i in range(n):
                if P[i] == 1:
                    total += A[i]
                else:
                    total += B[i]
            k = sum(P)
            res[k].append(total % M)

        for k in range(n + 1):
            res[k].sort()
        return res

    S = calc(G[::2], H[::2])
    T = calc(G[1::2], H[1::2])

    Q = int(input())
    ans = [0] * Q
    for q in range(Q):
        K, X = map(int, input().split())
        for k in range(N // 2 + 1):
            l = K - k
            if 0 <= l <= N // 2:
                for a in S[k]:
                    ans[q] += Binary_Search_Range_Count(T[l], X - a, M - a, False, True, False)
                    ans[q] += Binary_Search_Range_Count(T[l], M + X - a, 2 * M - a, False, True, False)
    return ans

#==================================================
print(*solve(), sep = "\n")
0