結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 142 ms
77,312 KB
testcase_01 AC 140 ms
77,568 KB
testcase_02 AC 214 ms
77,928 KB
testcase_03 AC 538 ms
78,260 KB
testcase_04 AC 390 ms
78,216 KB
testcase_05 AC 197 ms
77,824 KB
testcase_06 AC 454 ms
78,396 KB
testcase_07 AC 474 ms
78,116 KB
testcase_08 AC 255 ms
77,812 KB
testcase_09 AC 366 ms
78,660 KB
testcase_10 AC 481 ms
78,412 KB
testcase_11 AC 222 ms
78,156 KB
testcase_12 AC 555 ms
78,464 KB
testcase_13 AC 585 ms
78,420 KB
testcase_14 AC 542 ms
78,500 KB
testcase_15 AC 520 ms
78,032 KB
testcase_16 AC 538 ms
78,680 KB
testcase_17 AC 536 ms
78,336 KB
testcase_18 AC 571 ms
79,000 KB
testcase_19 AC 626 ms
78,984 KB
testcase_20 AC 590 ms
77,760 KB
testcase_21 AC 610 ms
78,868 KB
testcase_22 AC 1,325 ms
77,712 KB
testcase_23 AC 1,040 ms
77,780 KB
testcase_24 AC 1,082 ms
77,944 KB
testcase_25 AC 1,040 ms
77,508 KB
testcase_26 AC 1,316 ms
77,656 KB
testcase_27 AC 77 ms
75,648 KB
testcase_28 AC 95 ms
76,416 KB
testcase_29 AC 973 ms
78,272 KB
testcase_30 AC 474 ms
78,756 KB
testcase_31 AC 546 ms
78,204 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