結果

問題 No.3436 [Cherry 8th Tune B] この夏に何が起こるかな?
コンテスト
ユーザー atcoder8
提出日時 2026-01-24 00:19:08
言語 Rust
(1.92.0 + proconio + num + itertools)
結果
WA  
実行時間 -
コード長 3,155 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 5,842 ms
コンパイル使用メモリ 222,064 KB
実行使用メモリ 16,676 KB
最終ジャッジ日時 2026-01-24 00:28:05
合計ジャッジ時間 109,998 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 16 WA * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use itertools::{Itertools, enumerate, izip};
use proconio::{input, marker::Usize1};

fn main() {
    input! {
        q: usize,
    }

    let output = (0..q)
        .map(|_| {
            let (i, j) = solve();
            format!("{} {}", i + 1, j + 1)
        })
        .join("\n");
    println!("{output}");
}

fn solve() -> (usize, usize) {
    input! {
        (n, m, k, p): (usize, usize, usize, usize),
        tt: [u64; n],
        cc: [Usize1; n],
        bb: [u64; m],
        dd: [Usize1; m],
        ss: [u64; k],
    }

    let tops = enumerate(izip!(&tt, &cc))
        .map(|(i, (&t, &c))| Suit::new(i, t, c))
        .collect_vec();
    let bottoms = enumerate(izip!(&bb, &dd))
        .map(|(i, (&b, &d))| Suit::new(i, b, d))
        .sorted_unstable_by_key(|suit| (suit.cost, suit.color))
        .collect_vec();

    let mut bottom_by_color = vec![vec![]; k];
    for &bottom in &bottoms {
        bottom_by_color[bottom.color].push(bottom);
    }

    let is_ok = |max_cost: u64| {
        let num_combs = tops
            .iter()
            .map(|top| {
                if top.cost > max_cost {
                    return 0;
                }

                let max_rem_cost = max_cost - top.cost;

                let whole_upper = bottoms.partition_point(|bottom| bottom.cost <= max_rem_cost);
                let upper_without_discount = bottom_by_color[top.color]
                    .partition_point(|bottom| bottom.cost <= max_rem_cost);
                let upper_with_discount = bottom_by_color[top.color]
                    .partition_point(|bottom| bottom.cost <= max_rem_cost + ss[top.color]);
                whole_upper + upper_with_discount - upper_without_discount
            })
            .sum::<usize>();
        num_combs >= p
    };

    let mut ok = 2 * 10_u64.pow(9);
    let mut ng = 0_u64;
    while ok.abs_diff(ng) > 1 {
        let mid = (ok + ng) / 2;
        if is_ok(mid) {
            ok = mid;
        } else {
            ng = mid;
        }
    }

    for (top_id, top) in enumerate(&tops) {
        if top.cost > ok {
            continue;
        }

        let rem_cost = ok - top.cost;

        let lower = bottoms.partition_point(|bottom| bottom.cost < rem_cost);
        let upper = bottoms.partition_point(|bottom| bottom.cost <= rem_cost);
        if lower < upper {
            if bottoms[lower].color != top.color {
                return (top_id, bottoms[lower].id);
            }
            if bottoms[upper - 1].color != top.color {
                return (top_id, bottoms[upper - 1].id);
            }
        }

        let lower = bottom_by_color[top.color]
            .partition_point(|bottom| bottom.cost < rem_cost + ss[top.color]);
        let upper = bottom_by_color[top.color]
            .partition_point(|bottom| bottom.cost <= rem_cost + ss[top.color]);
        if lower < upper {
            return (top_id, bottoms[lower].id);
        }
    }

    (100, 100)
}

#[derive(Debug, Clone, Copy)]
struct Suit {
    id: usize,
    cost: u64,
    color: usize,
}

impl Suit {
    fn new(id: usize, cost: u64, color: usize) -> Self {
        Self { id, cost, color }
    }
}
0