#1170389 (Rust) No.2114 01 Matching

• 問題: No.2114 01 Matching
• ユーザー: akakimidori
• 提出日時: 2026-07-04 05:08:17
• 言語: Rust (1.94.0 + proconio + num + itertools)
• 結果: AC
• 実行時間: 119 ms / 5,000 ms
• コード長: 7,570 bytes
• コンパイル時間: 5,092 ms
• コンパイル使用メモリ: 203,200 KB
• 実行使用メモリ: 31,340 KB
• 最終ジャッジ日時: 2026-07-04 05:08:34
• 合計ジャッジ時間: 11,276 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 b = b.into_iter().map(|b| (b % k, b / k)).collect::<Vec<_>>();
    let mut r = r.into_iter().map(|r| (r % k, r / k)).collect::<Vec<_>>();
    b.sort();
    r.sort();
    let mut sum = 0;
    let mut cnt = 0;
    let mut x = 0;
    let mut y = 0;
    while x < b.len() && y < r.len() {
        let v = b[x].0.min(r[y].0);
        let b = b[x..].iter().take_while(|b| b.0 == v).map(|b| b.1).collect::<Vec<_>>();
        let r = r[y..].iter().take_while(|b| b.0 == v).map(|b| b.1).collect::<Vec<_>>();
        x += b.len();
        y += r.len();
        let dp = matching1d(b, r);
        sum += *dp.last().unwrap();
        cnt += dp.len() - 1;
    }
    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 = FastSet::build(z.len(), 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.prev(l);
        let nr = set.next(r);
        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 ----------
pub struct FastSet {
    size: usize,
    seg: Vec<Vec<usize>>,
}

impl FastSet {
    pub fn build<I>(size: usize, init: I) -> Self
    where
        I: Iterator<Item = usize>
    {
        assert!(size > 0);
        let mut n = size;
        let w = std::mem::size_of::<usize>() * 8;
        let mut seg = vec![];
        let mut data = vec![0; (n + w - 1) / w];
        for x in init {
            assert!(x < size);
            data[x / w] |= 1 << (x % w);
        }
        seg.push(data);
        while n > 1 {
            n = (n + w - 1) / w;
            let d = seg.last().unwrap().chunks(w).map(|a| {
                a.iter().enumerate().filter(|p| *p.1 > 0).fold(0, |s, a| s | (1 << a.0))
            }).collect::<Vec<_>>();
            seg.push(d);
        }
        Self { size, seg }
    }
    pub fn new(size: usize) -> Self {
        let mut n = size;
        let w = std::mem::size_of::<usize>() * 8;
        let mut seg = vec![];
        while {
            let m = (n + w - 1) / w;
            seg.push(vec![0; m]);
            n = m;
            n > 1
        } {}
        Self { size, seg }
    }
    pub fn insert(&mut self, mut x: usize) -> bool {
        assert!(x < self.size);
        let w = std::mem::size_of::<usize>() * 8;
        let seg = &mut self.seg;
        if seg[0][x / w] >> (x % w) == 1 {
            return false;
        }
        for seg in seg.iter_mut() {
            seg[x / w] |= 1 << (x % w);
            x /= w;
        }
        true
    }
    pub fn remove(&mut self, mut x: usize) -> bool {
        assert!(x < self.size);
        let w = std::mem::size_of::<usize>() * 8;
        let seg = &mut self.seg;
        if seg[0][x / w] >> (x % w) == 0 {
            return false;
        }
        for seg in seg.iter_mut() {
            seg[x / w] &= !(1 << (x % w));
            if seg[x / w] != 0 {
                break;
            }
            x /= w;
        }
        true
    }
    pub fn contains(&self, x: usize) -> bool {
        assert!(x < self.size);
        let w = std::mem::size_of::<usize>() * 8;
        self.seg[0][x / w] >> (x % w) & 1 == 1
    }
    pub fn next(&self, mut x: usize) -> Option<usize> {
        if x >= self.size {
            return None;
        }
        let w = std::mem::size_of::<usize>() * 8;
        let seg = &self.seg;
        for (i, s) in seg.iter().enumerate() {
            if x / w == s.len() {
                return None;
            }
            if s[x / w] >> (x % w) == 0 {
                x = x / w + 1;
                continue;
            }
            let k = (s[x / w] >> (x % w)).trailing_zeros() as usize;
            x += k;
            for seg in seg[..i].iter().rev() {
                let k = seg[x].trailing_zeros() as usize;
                x = w * x + k;
            }
            return Some(x)
        }
        None
    }
    pub fn prev(&self, mut x: usize) -> Option<usize> {
        x = x.min(self.size - 1);
        let w = std::mem::size_of::<usize>() * 8;
        let seg = &self.seg;
        for (i, s) in seg.iter().enumerate() {
            let d = s[x / w] << (w - 1 - x % w);
            if d == 0 {
                if x < w {
                    break;
                }
                x = x / w - 1;
                continue;
            }
            let k = d.leading_zeros() as usize;
            x -= k;
            for seg in seg[..i].iter().rev() {
                let k = w - 1 - seg[x].leading_zeros() as usize;
                x = w * x + k;
            }
            return Some(x);
        }
        None
    }
}