#1170379 (Rust) No.2114 01 Matching

• 問題: No.2114 01 Matching
• ユーザー: akakimidori
• 提出日時: 2026-07-04 04:53:50
• 言語: Rust (1.94.0 + proconio + num + itertools)
• 結果: AC
• 実行時間: 350 ms / 5,000 ms
• コード長: 3,920 bytes
• コンパイル時間: 12,397 ms
• コンパイル使用メモリ: 201,256 KB
• 実行使用メモリ: 73,472 KB
• 最終ジャッジ日時: 2026-07-04 04:54:21
• 合計ジャッジ時間: 22,324 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

ファイルパターン	結果
sample	AC * 2
other	AC * 51

ソースコード

fn main() {
    input! {
        n: usize,
        m: usize,
        k: i64,
        b: [i64; n],
        r: [i64; m],
    }
    let mut map = std::collections::BTreeMap::new();
    for &b in b.iter() {
        map.entry(b % k).or_insert(vec![vec![]; 2])[0].push(b / k);
    }
    for &r in r.iter() {
        map.entry(r % k).or_insert(vec![vec![]; 2])[1].push(r / k);
    }
    let mut sum = 0;
    let mut cnt = 0;
    for (_, mut p) in map {
        let a = std::mem::take(&mut p[0]);
        let b = std::mem::take(&mut p[1]);
        let dp = matching1d(a, b);
        cnt += dp.len() - 1;
        sum += *dp.last().unwrap();
    }
    if cnt == n.min(m) {
        println!("{}", sum);
    } else {
        println!("-1");
    }
}

// A_i と B_j をマッチさせるときに |A_i - B_j| のコスト
// k 個(0 <= k <= min(|A|, |B|)) マッチングを作るときの最小コスト
fn matching1d(a: Vec<i64>, b: Vec<i64>) -> Vec<i64> {
    let m = b.len();
    let mut z = vec![];
    z.extend(a.into_iter().map(|a| (a, 0)));
    z.extend(b.into_iter().map(|a| (a, 1)));
    z.sort();
    let mut sum = vec![0; z.len() + 1];
    let mut last = vec![z.len() + 1; z.len() + 1];
    let mut pos = m;
    last[pos] = z.len();
    for (i, &(x, op)) in z.iter().enumerate().rev() {
        if op == 1 {
            pos -= 1;
        } else {
            pos += 1;
        }
        let r = last[pos];
        if r < sum.len() {
            sum[i] = (z[r - 1].0 - x).abs() + sum[i + 1] - sum[r - 1] + sum[r];
        }
        last[pos] = i;
    }
    let mut set = std::collections::BTreeSet::new();
    set.extend(0..z.len());
    let mut h = std::collections::BinaryHeap::new();
    for (i, z) in z.windows(2).enumerate() {
        if z[0].1 != z[1].1 {
            let d = sum[i] - sum[i + 2];
            h.push((-d, i, i + 1));
        }
    }
    let mut ans = vec![0];
    while let Some((d, l, r)) = h.pop() {
        if !set.contains(&l) || !set.contains(&r) {
            continue;
        }
        let v = *ans.last().unwrap() - d;
        ans.push(v);
        set.remove(&l);
        set.remove(&r);
        let nl = set.range(..l).next_back();
        let nr = set.range(r..).next();
        let nlr = nl.zip(nr);
        if nlr.map_or(false, |(s, t)| z[*s].1 != z[*t].1) {
            let (&s, &t) = nlr.unwrap();
            let d = sum[s] - sum[t + 1] - (sum[s + 1] - sum[t]);
            h.push((-d, s, t));
        }
    }
    ans
}

// ---------- begin input macro ----------
// reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[macro_export]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

#[macro_export]
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

#[macro_export]
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, bytes) => {
        read_value!($iter, String).bytes().collect::<Vec<u8>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
// ---------- end input macro ----------