提出 #57822711

---

ソースコード 拡げる

#![allow(non_snake_case)]

use proconio::input;

fn main() {
    get_time();
    input! {
        n: usize,
        mut ps: [(i32, i32); n],
    }
    ps.sort_by_key(|p| p.0 + p.1);
    let mut hash = 0;
    for &p in &ps {
        hash += f(p);
    }
    let mut beam = vec![State {
        ps,
        id: !0,
        eval: 0,
        hash,
    }];
    let mut trace = Trace::new();
    for _ in 0..n - 1 {
        let mut cand = BoundedSortedList::new(2200);
        for k in 0..beam.len() {
            let State { ref ps, eval, .. } = beam[k];
            for i in (0..ps.len()).rev() {
                if !cand.can_insert(Reverse(eval + ps[i].0 as i64 + ps[i].1 as i64)) {
                    break;
                }
                for j in (0..i).rev() {
                    if !cand.can_insert(Reverse(eval + ps[j].0 as i64 + ps[j].1 as i64)) {
                        break;
                    }
                    let d = (ps[i].0.min(ps[j].0) + ps[i].1.min(ps[j].1)) as i64;
                    if cand.can_insert(Reverse(eval + d)) {
                        cand.insert(Reverse(eval + d), (k, i, j));
                    }
                }
            }
        }
        let mut next = vec![];
        let mut used = FxHashSet::default();
        for (Reverse(eval), (k, i, j)) in cand.list() {
            let p = beam[k].ps[i];
            let q = beam[k].ps[j];
            let r = (p.0.min(q.0), p.1.min(q.1));
            let hash = beam[k].hash - f(p) - f(q) + f(r);
            if !used.insert(hash) {
                continue;
            }
            let mut ps = beam[k].ps.clone();
            ps.remove(i);
            ps.remove(j);
            ps.push(r);
            let id = trace.add((r, p), beam[k].id);
            let id = trace.add((r, q), id);
            next.push(State { ps, id, eval, hash });
        }
        beam = next;
    }
    assert_eq!(beam.len(), 1);
    let id = beam[0].id;
    let mut out = trace.get(id);
    out.reverse();
    write_output(&out);
    eprintln!("Time = {:.3}", get_time());
}

fn f(p: (i32, i32)) -> i64 {
    (p.0 as i64 + 1) * 1000000007 + p.1 as i64 + 1
}

struct State {
    ps: Vec<(i32, i32)>,
    id: usize,
    eval: i64,
    hash: i64,
}

fn write_output(out: &Vec<((i32, i32), (i32, i32))>) {
    println!("{}", out.len());
    for ((x1, y1), (x2, y2)) in out {
        println!("{} {} {} {}", x1, y1, x2, y2);
    }
}

// ここからライブラリ

pub trait SetMinMax {
    fn setmin(&mut self, v: Self) -> bool;
    fn setmax(&mut self, v: Self) -> bool;
}
impl<T> SetMinMax for T
where
    T: PartialOrd,
{
    fn setmin(&mut self, v: T) -> bool {
        *self > v && {
            *self = v;
            true
        }
    }
    fn setmax(&mut self, v: T) -> bool {
        *self < v && {
            *self = v;
            true
        }
    }
}

#[macro_export]
macro_rules! mat {
	($($e:expr),*) => { vec![$($e),*] };
	($($e:expr,)*) => { vec![$($e),*] };
	($e:expr; $d:expr) => { vec![$e; $d] };
	($e:expr; $d:expr $(; $ds:expr)+) => { vec![mat![$e $(; $ds)*]; $d] };
}

pub fn get_time() -> f64 {
    static mut STIME: f64 = -1.0;
    let t = std::time::SystemTime::now()
        .duration_since(std::time::UNIX_EPOCH)
        .unwrap();
    let ms = t.as_secs() as f64 + t.subsec_nanos() as f64 * 1e-9;
    unsafe {
        if STIME < 0.0 {
            STIME = ms;
        }
        // ローカル環境とジャッジ環境の実行速度差はget_timeで吸収しておくと便利
        #[cfg(feature = "local")]
        {
            (ms - STIME) * 1.0
        }
        #[cfg(not(feature = "local"))]
        {
            ms - STIME
        }
    }
}

pub struct Trace<T: Copy> {
    log: Vec<(T, usize)>,
}

impl<T: Copy> Trace<T> {
    pub fn new() -> Self {
        Trace { log: vec![] }
    }
    pub fn add(&mut self, c: T, p: usize) -> usize {
        self.log.push((c, p));
        self.log.len() - 1
    }
    pub fn get(&self, mut i: usize) -> Vec<T> {
        let mut out = vec![];
        while i != !0 {
            out.push(self.log[i].0);
            i = self.log[i].1;
        }
        out.reverse();
        out
    }
}

use rustc_hash::FxHashSet;
use std::{cmp::Reverse, collections::BinaryHeap};

#[derive(Clone, Debug)]
struct Entry<K, V> {
    k: K,
    v: V,
}

impl<K: PartialOrd, V> Ord for Entry<K, V> {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.partial_cmp(other).unwrap()
    }
}

impl<K: PartialOrd, V> PartialOrd for Entry<K, V> {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        self.k.partial_cmp(&other.k)
    }
}

impl<K: PartialEq, V> PartialEq for Entry<K, V> {
    fn eq(&self, other: &Self) -> bool {
        self.k.eq(&other.k)
    }
}

impl<K: PartialEq, V> Eq for Entry<K, V> {}

/// K が小さいトップn個を保持
#[derive(Clone, Debug)]
pub struct BoundedSortedList<K: PartialOrd + Copy, V: Clone> {
    que: BinaryHeap<Entry<K, V>>,
    size: usize,
}

impl<K: PartialOrd + Copy, V: Clone> BoundedSortedList<K, V> {
    pub fn new(size: usize) -> Self {
        Self {
            que: BinaryHeap::with_capacity(size),
            size,
        }
    }
    pub fn can_insert(&self, k: K) -> bool {
        self.que.len() < self.size || self.que.peek().unwrap().k > k
    }
    pub fn insert(&mut self, k: K, v: V) {
        if self.que.len() < self.size {
            self.que.push(Entry { k, v });
        } else if let Some(mut top) = self.que.peek_mut() {
            if top.k > k {
                top.k = k;
                top.v = v;
            }
        }
    }
    pub fn list(&self) -> Vec<(K, V)> {
        let v = self.que.clone().into_sorted_vec();
        v.into_iter().map(|e| (e.k, e.v)).collect()
    }
    pub fn len(&self) -> usize {
        self.que.len()
    }
}

提出情報

ジャッジ結果