提出 #57824394

---

ソースコード 拡げる

#![allow(non_snake_case, dead_code)]
use itertools::Itertools;
use rand::prelude::*;
use rand_pcg::Pcg64Mcg;
type Mt = Pcg64Mcg;

#[derive(Clone, Default, PartialEq, PartialOrd, Ord, Eq)]
struct P {
    x: i64,
    y: i64,
}

impl P {
    pub fn ancestor(&self, p: &P) -> (P, i64) {
        let a = P { x: self.x.min(p.x), y: self.y.min(p.y) };
        let c = self.x - a.x 
            + self.y - a.y 
            + p.x - a.x
            + p.y - a.y;
        (a, c)
    }
}

type Input = Vec<P>;

struct Operation {
    from: P,
    to: Vec<P>,
}

struct Answer {
    ops: Vec<Operation>,
}

impl Answer {
    fn output(self) {
        let mut len = 0;
        for Operation { from, to } in self.ops.iter() {
            len += to.len();
        }
        println!("{}", len);
        for Operation { from, to } in self.ops {
            for P { x, y } in to {
                println!("{} {} {} {}", from.x, from.y, x, y);
            }
        }
    }
}

struct Node {
    p: P,
    leaf: bool,
    sz: usize,
    cost: i64,
}

struct State {
     ett: Vec<Node>,
}

struct Neiborhood {
    from: usize,
    delete_v: usize,
    to: usize,
    score: i64,
}

impl Neiborhood {
    fn gen(state: &State, mt: &mut Mt) -> Self {
         loop {
             let from = mt.gen_range(1..state.ett.len());
             let moved_l = from;
             let moved_r = from + state.ett[from].sz;
             let mut delete_v = !0;
             let mut until = vec![(!0, P::default()); state.ett.len()];
             let mut merged = vec![(!0, P::default(), !0); state.ett.len()];
             for i in (0..state.ett.len()).rev() {
                 if moved_l <= i && i < moved_r { continue; }
                 if state.ett[i].leaf {
                     until[i] = (0, state.ett[i].p.clone());
                     let (a, c) = state.ett[i].p.ancestor(&state.ett[from].p);
                     merged[i] = (c + state.ett[from].cost, a, i);
                 }
                 else {
                     let l = i + 1;
                     let r = i + 1 + state.ett[l].sz;
                     if r == from {
                         until[i] = until[l].clone();
                         merged[i] = merged[l].clone();
                         delete_v = i;
                     }
                     else if l == from {
                         until[i] = until[r].clone();
                         merged[i] = merged[r].clone();
                         delete_v = i;
                     }
                     else {
                         let (a, c) = until[l].1.ancestor(&until[r].1);
                         until[i] = (c + until[l].0 + until[r].0, a);
                         let (a, c) = until[i].1.ancestor(&state.ett[from].p);
                         merged[i] = (c + until[i].0 + state.ett[from].cost, a, i);
                         let (a, c) = until[l].1.ancestor(&merged[r].1);
                         merged[i] = merged[i].clone().min((c + until[l].0 + merged[r].0, a, merged[r].2));
                         let (a, c) = merged[l].1.ancestor(&until[r].1);
                         merged[i] = merged[i].clone().min((c + merged[l].0 + until[r].0, a, merged[l].2));
                     }
                 }
             }
             let to = merged[0].2;
             let score = merged[0].0 + merged[0].1.x + merged[0].1.y;
             return Neiborhood { from, delete_v, to, score };
         }
    }
    fn accept(&self, state: &mut State) {
        let moved_l = self.from;
        let moved_r = self.from + state.ett[self.from].sz;
        let mut to = self.to;
        if moved_l <= to {
            to -= 1 + state.ett[self.from].sz;
        }
        else if self.delete_v <= to {
            to -= 1;
        }
        let mv = state.ett.drain(moved_l..moved_r).collect_vec();
        state.ett.remove(self.delete_v);
        state.ett.splice(to..to, mv);
        state.ett.insert(to, Node { p: P::default(), leaf: false, sz: 0, cost: 0});
        state.all_fix();
    }
}

impl State {
    fn new(input: &Input) -> Self {
        let mut ett = vec![];
        let mut st = vec![];
        st.push((0, input.len()));
        while let Some((l, r)) = st.pop() {
            if l + 1 == r {
                ett.push(Node { p: input[l].clone(), leaf: true, sz: 1, cost: 0 });
            }
            else {
                ett.push(Node { p: P::default(), leaf: false, sz: r - l + r - l - 1, cost: 0 });
                st.push((l, (l + r) >> 1));
                st.push(((l + r) >> 1, r));
            }
        }
        let mut state = State { ett };
        state.all_fix();
        state
    }
    fn all_fix(&mut self) {
        for i in (0..self.ett.len()).rev() {
            if !self.ett[i].leaf {
                let l = i + 1;
                let r = i + 1 + self.ett[l].sz;
                let (a, c) = self.ett[l].p.ancestor(&self.ett[r].p);
                self.ett[i].p = a;
                self.ett[i].sz = self.ett[l].sz + self.ett[r].sz + 1;
                self.ett[i].cost = self.ett[l].cost + self.ett[r].cost + c;
            }
        }
    }
    fn score(&self) -> i64 {
        self.ett[0].cost + self.ett[0].p.x + self.ett[0].p.y
    }

    fn answer(&self) -> Answer {
        let mut ops = vec![];
        ops.push( Operation { from: P { x: 0, y: 0 }, to: vec![self.ett[0].p.clone()] });
        for i in 0..self.ett.len() {
            if !self.ett[i].leaf {
                let l = i + 1;
                let r = i + 1 + self.ett[l].sz;
                ops.push( Operation {
                    from: self.ett[i].p.clone(),
                    to: vec![self.ett[l].p.clone(), self.ett[r].p.clone()],
                })
            }
        }

        Answer { ops }
    }

    fn metropolis(&mut self, t: f64, mt: &mut Mt) {
        let now_score = self.score();
        let nbh = Neiborhood::gen(self, mt);
        //eprintln!("{} {}", nbh.score, now_score);
        let delta = (nbh.score - now_score) as f64;
        if delta <= 0.0 || mt.gen_bool((-delta / t).exp()) {
            nbh.accept(self);
            //eprintln!("{} {}", self.score(), nbh.score);
            //assert_eq!(self.score(), nbh.score);
        }
    }
}

fn main() {
    get_time();
    let input = get_input();

    let mut state = State::new(&input);
    let mut mt = Mt::new(768);
    let T0 = 1000000000.0f64;
    let T1 = 100000.0f64;
    let mut T = T0;
    let mut it = 0;
    loop {
        let time = get_time();
        if time > 1.95 {
            break;
        }
        it += 1;
        if it % 1000 == 0 {
            eprintln!("{} {}", T, state.score());
            T = T0.powf(1.0 - time / 2.0) * T1.powf(time / 2.0);
        }
        state.metropolis(T, &mut mt);
    }
    eprintln!("score: {}", state.ett[0].cost + state.ett[0].p.x + state.ett[0].p.y);
    let answer = state.answer();
    answer.output();
}

fn get_input() -> Input {
    proconio::input! {
        n: usize,
        xy: [(i64, i64); n],
    }
    xy.into_iter().map(|(x, y)| P { x, y }).collect()
}
// must call first to set zero
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;
        }
        #[cfg(feature = "local")]
        {
            (ms - STIME) * 1.0
        }
        #[cfg(not(feature = "local"))]
        {
            ms - STIME
        }
    }
}

提出情報

コンパイルエラー

warning: unused variable: `from`
  --> src/main.rs:38:25
   |
38 |         for Operation { from, to } in self.ops.iter() {
   |                         ^^^^ help: try ignoring the field: `from: _`
   |
   = note: `#[warn(unused_variables)]` on by default

ジャッジ結果