結果

問題 No.2581 [Cherry Anniversary 3] 28輪の桜のブーケ
コンテスト
ユーザー 👑 Kazun
提出日時 2023-11-12 22:03:48
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,325 ms / 3,000 ms
コード長 2,974 bytes
コンパイル時間 286 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 79,000 KB
最終ジャッジ日時 2024-09-27 03:15:30
合計ジャッジ時間 18,937 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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