結果

問題 No.3436 [Cherry 8th Tune B] この夏に何が起こるかな?
コンテスト
ユーザー urectanc
提出日時 2026-01-23 23:19:59
言語 Rust
(1.92.0 + proconio + num + itertools)
結果
AC  
実行時間 223 ms / 4,000 ms
コード長 2,432 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,282 ms
コンパイル使用メモリ 218,572 KB
実行使用メモリ 13,732 KB
最終ジャッジ日時 2026-01-23 23:20:20
合計ジャッジ時間 18,830 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 43
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use std::collections::BTreeSet;

use proconio::{fastout, input, marker::Usize1};

#[fastout]
fn main() {
    input! { t: usize }

    for _ in 0..t {
        let (i, j) = solve();
        println!("{} {}", i + 1, j + 1);
    }
}

fn solve() -> (usize, usize) {
    input! {
        n: usize, m: usize, k: usize, p: usize,
        p0: [i64; n],
        c0: [Usize1; n],
        p1: [i64; m],
        c1: [Usize1; m],
        s: [i64; k],
    }

    // let mut naive = vec![];
    // for i in 0..n {
    //     for j in 0..m {
    //         let mut p = p0[i] + p1[j];
    //         if c0[i] == c1[j] {
    //             p -= s[c0[i]];
    //         }
    //         naive.push(p);
    //     }
    // }
    // naive.sort_unstable();
    // eprintln!("{} {naive:?}", naive[p - 1]);

    let mut bottom_by_color = vec![vec![]; k];
    for (&p, &c) in p1.iter().zip(&c1) {
        bottom_by_color[c].push(p);
    }
    for v in &mut bottom_by_color {
        v.sort_unstable();
    }

    let mut bottom = p1.clone();
    bottom.sort_unstable();

    let check = |threshold: i64| {
        let mut cnt = 0;

        for (&p0, &c0) in p0.iter().zip(&c0) {
            cnt += bottom.partition_point(|&x| x + p0 <= threshold);
            cnt += bottom_by_color[c0].partition_point(|&x| x + p0 <= threshold + s[c0]);
            cnt -= bottom_by_color[c0].partition_point(|&x| x + p0 <= threshold);
        }

        cnt >= p
    };

    let mut ng = 0;
    let mut ok = 1i64 << 32;
    while ok.abs_diff(ng) > 1 {
        let mid = ok.midpoint(ng);
        if check(mid) {
            ok = mid;
        } else {
            ng = mid;
        }
    }
    // eprintln!("{ok}");

    let mut bottom = BTreeSet::new();
    for (i, (&p, &c)) in p1.iter().zip(&c1).enumerate() {
        bottom.insert((p, c, i));
    }
    for i in 0..n {
        let p0 = p0[i];
        let c0 = c0[i];

        let target = ok - p0;

        if let Ok(_) = bottom_by_color[c0].binary_search(&(target + s[c0])) {
            let j = (0..m)
                .find(|&j| c1[j] == c0 && p1[j] == target + s[c0])
                .unwrap();
            return (i, j);
        }

        if let Some(&(_, _, j)) = bottom.range((target, 0, 0)..(target, c0, 0)).next() {
            return (i, j);
        }
        if let Some(&(_, _, j)) = bottom.range((target, c0 + 1, 0)..(target, k, 0)).next() {
            return (i, j);
        }
    }

    unreachable!()
}
0