結果

問題 No.3436 [Cherry 8th Tune B] この夏に何が起こるかな?
コンテスト
ユーザー 👑 Kazun
提出日時 2025-03-17 01:34:01
言語 PyPy3
(7.3.17)
結果
AC  
実行時間 1,854 ms / 4,000 ms
コード長 3,993 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 461 ms
コンパイル使用メモリ 82,752 KB
実行使用メモリ 127,136 KB
最終ジャッジ日時 2026-01-23 21:14:52
合計ジャッジ時間 57,290 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 43
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def General_Binary_Increase_Search_Integer(L, R, cond, default=None):
    """ 条件式が単調増加であるとき, 整数上で二部探索を行い, cond(x) が真になる最小の整数 x を求める.

    L: 解の下限
    R: 解の上限
    cond: 条件(1変数関数, 広義単調増加を満たす)
    default: R で条件を満たさない (つまり, [L, R] 上では常に偽) ときの返り値
    """

    if not(cond(R)):
        return default

    if cond(L):
        return L

    R+=1
    while R-L>1:
        C=L+(R-L)//2
        if cond(C):
            R=C
        else:
            L=C
    return R

#==================================================
import dataclasses

@dataclasses.dataclass
class Top:
    id: int
    price: int
    color: int

@dataclasses.dataclass
class Bottom:
    id: int
    price: int
    color: int

#==================================================
def input_integers() -> str:
    return list(map(int, input().split()))

def solve():
    from operator import attrgetter

    N, M, K, P = map(int, input().split())
    T = input_integers()
    C = input_integers()
    B = input_integers()
    D = input_integers()
    S = [0] + input_integers()

    tops = [Top(i, T[i - 1], C[i - 1]) for i in range(1, N + 1)]
    tops_sort = sorted(tops, key = attrgetter('price'))
    color_tops: list[list[Top]] = [[] for _ in range(K + 1)]
    for top in tops_sort:
        color_tops[top.color].append(top)

    bottoms = [Bottom(j, B[j - 1], D[j - 1]) for j in range(1, M + 1)]
    bottoms_sort = sorted(bottoms, key = attrgetter('price'))
    color_bottoms: list[list[Bottom]] = [[] for _ in range(K + 1)]
    for bottom in bottoms_sort:
        color_bottoms[bottom.color].append(bottom)

    # Section I: 「X 円以下のセットが P 組以上」を満たす最小の非負整数 X を求める.
    def count_pairs_less_price(tops: list[Top], bottoms: list[Top], X: int) -> int:
        res = 0
        j = len(bottoms)
        for top in tops:
            while (j > 0) and (top.price + bottoms[j - 1].price > X):
                j -= 1

            res += j
        return res

    def check(X: int) -> bool:
        res = count_pairs_less_price(tops_sort, bottoms_sort, X)
        for k in range(1, K + 1):
            res += count_pairs_less_price(color_tops[k], color_bottoms[k], X + S[k])
            res -= count_pairs_less_price(color_tops[k], color_bottoms[k], X)
        return res >= P

    X = General_Binary_Increase_Search_Integer(0, 3 * 10 ** 9, check)

    # Section II: 価格がちょうど X である組み合わせを求める
    bottom_price_count = {}
    for bottom in bottoms:
        bottom_price_count[bottom.price] = bottom_price_count.get(bottom.price, 0) + 1

    for k in range(1, K + 1):
        # Case A: 同じ色同士のペア
        color_bottoms_price_set = set(bottom.price for bottom in color_bottoms[k])
        for top in color_tops[k]:
            if (y := ((X + S[k]) - top.price)) in color_bottoms_price_set:
                for bottom in color_bottoms[k]:
                    if bottom.price == y:
                        break
                return top.id, bottom.id

        # Case B: 異なる色通しのペア
        # 色 k のカウントを除く
        for bottom in color_bottoms[k]:
            bottom_price_count[bottom.price] -= 1

        for top in color_tops[k]:
            if bottom_price_count.get(X - top.price, 0) == 0:
                continue

            for bottom in bottoms:
                if (top.price + bottom.price == X) and (top.color != bottom.color):
                    return top.id, bottom.id

        # 色 k のカウントを復活
        for bottom in color_bottoms[k]:
            bottom_price_count[bottom.price] += 1

#==================================================
import sys
input = sys.stdin.readline
write = sys.stdout.write

T = int(input())
write("\n".join(map(lambda ans: f"{ans[0]} {ans[1]}", [solve() for _ in range(T)])))
0