#955568 (Rust) No.5020 Averaging

• 問題: No.5020 Averaging
• ユーザー: hangry
• 提出日時: 2024-02-25 16:04:32
• 言語: Rust (1.77.0)
• 結果: AC
• 実行時間: 952 ms / 1,000 ms
• コード長: 17,775 bytes
• コンパイル時間: 1,210 ms
• コンパイル使用メモリ: 195,384 KB
• 実行使用メモリ: 6,676 KB
• スコア: 15,188,399
• 最終ジャッジ日時: 2024-02-25 16:05:32
• 合計ジャッジ時間: 51,519 ms
• ジャッジサーバーID （参考情報）: judge13 / judge14

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	952 ms; 6,676 KB
testcase_01	AC	952 ms; 6,676 KB
testcase_02	AC	952 ms; 6,676 KB
testcase_03	AC	952 ms; 6,676 KB
testcase_04	AC	951 ms; 6,676 KB
testcase_05	AC	951 ms; 6,676 KB
testcase_06	AC	952 ms; 6,676 KB
testcase_07	AC	952 ms; 6,676 KB
testcase_08	AC	952 ms; 6,676 KB
testcase_09	AC	952 ms; 6,676 KB
testcase_10	AC	952 ms; 6,676 KB
testcase_11	AC	952 ms; 6,676 KB
testcase_12	AC	952 ms; 6,676 KB
testcase_13	AC	952 ms; 6,676 KB
testcase_14	AC	951 ms; 6,676 KB
testcase_15	AC	951 ms; 6,676 KB
testcase_16	AC	952 ms; 6,676 KB
testcase_17	AC	952 ms; 6,676 KB
testcase_18	AC	952 ms; 6,676 KB
testcase_19	AC	952 ms; 6,676 KB
testcase_20	AC	952 ms; 6,676 KB
testcase_21	AC	952 ms; 6,676 KB
testcase_22	AC	952 ms; 6,676 KB
testcase_23	AC	952 ms; 6,676 KB
testcase_24	AC	951 ms; 6,676 KB
testcase_25	AC	952 ms; 6,676 KB
testcase_26	AC	951 ms; 6,676 KB
testcase_27	AC	952 ms; 6,676 KB
testcase_28	AC	952 ms; 6,676 KB
testcase_29	AC	952 ms; 6,676 KB
testcase_30	AC	952 ms; 6,676 KB
testcase_31	AC	952 ms; 6,676 KB
testcase_32	AC	952 ms; 6,676 KB
testcase_33	AC	952 ms; 6,676 KB
testcase_34	AC	951 ms; 6,676 KB
testcase_35	AC	952 ms; 6,676 KB
testcase_36	AC	951 ms; 6,676 KB
testcase_37	AC	952 ms; 6,676 KB
testcase_38	AC	952 ms; 6,676 KB
testcase_39	AC	952 ms; 6,676 KB
testcase_40	AC	952 ms; 6,676 KB
testcase_41	AC	952 ms; 6,676 KB
testcase_42	AC	952 ms; 6,676 KB
testcase_43	AC	952 ms; 6,676 KB
testcase_44	AC	951 ms; 6,676 KB
testcase_45	AC	952 ms; 6,676 KB
testcase_46	AC	951 ms; 6,676 KB
testcase_47	AC	952 ms; 6,676 KB
testcase_48	AC	952 ms; 6,676 KB
testcase_49	AC	952 ms; 6,676 KB

ソースコード

#![allow(dead_code)]
#![allow(non_upper_case_globals)]
#![allow(unused_imports)]
use crate::{
    data_structures::{
        grid::{Coord, Map2d},
        *,
    },
    problem::*,
    sa::*,
    utils::*,
};
use std::{cmp::*, collections::*};

const TIME_LIMIT: f64 = 0.95;
const N: usize = 45;
const W: usize = 5 * 10usize.pow(17);

pub fn main() {
    get_time();
    let input = read_input();
    let output = solve(&input);
    output.print_ans();
    eprintln!("Time = {}", get_time());
}

fn solve(input: &Input) -> Output {
    let mut state = State::new(input);
    state.score = state.calc_score();
    let mut solver = SASolver::new(state.clone());
    solver.run(input, TIME_LIMIT - get_time());
    let cnt = solver.state.cnt;
    let sa_score = solver.state.calc_score();
    crate::printdata!(cnt, sa_score);
    solver.state.to_output(input)
}


mod data_structures {use super::*;

pub mod grid {
    #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
    pub struct Coord {
        pub x: usize,
        pub y: usize,
    }

    impl Coord {
        pub const fn new(x: usize, y: usize) -> Self {
            Self { x, y }
        }

        pub const fn new2(p: usize, width: usize) -> Self {
            Self {
                x: p / width,
                y: p % width,
            }
        }

        pub fn in_map(&self, size: usize) -> bool {
            self.x < size && self.y < size
        }

        pub const fn idx(&self, size: usize) -> usize {
            self.x * size + self.y
        }

        pub fn next(self, dir: usize) -> Self {
            self + DXY[dir]
        }

        pub const fn dist(&self, other: &Self) -> usize {
            Self::dist_1d(self.x, other.x) + Self::dist_1d(self.y, other.y)
        }

        const fn dist_1d(x0: usize, x1: usize) -> usize {
            x0.abs_diff(x1)
        }
    }

    impl std::ops::Add for Coord {
        type Output = Self;

        fn add(self, other: Self) -> Self {
            Self {
                x: self.x + other.x,
                y: self.y + other.y,
            }
        }
    }

    pub const DXY: [Coord; 4] = [
        Coord::new(0, !0),
        Coord::new(!0, 0),
        Coord::new(0, 1),
        Coord::new(1, 0),
    ];

    pub const DC: [char; 4] = ['L', 'U', 'R', 'D'];

    #[derive(Debug, Clone)]
    pub struct Map2d<T> {
        pub height: usize,
        pub width: usize,
        map: Vec<T>,
    }

    impl<T: Clone> Map2d<T> {
        pub fn new(map: Vec<T>, width: usize) -> Self {
            let height = map.len() / width;
            debug_assert!(width * height == map.len());
            Self { height, width, map }
        }

        pub fn fill(&mut self, value: T) {
            self.map.fill(value);
        }
    }

    impl<T> std::ops::Index<Coord> for Map2d<T> {
        type Output = T;

        #[inline]
        fn index(&self, coord: Coord) -> &Self::Output {
            unsafe { self.map.get_unchecked(coord.x * self.width + coord.y) }
        }
    }

    impl<T> std::ops::IndexMut<Coord> for Map2d<T> {
        #[inline]
        fn index_mut(&mut self, coord: Coord) -> &mut Self::Output {
            unsafe { self.map.get_unchecked_mut(coord.x * self.width + coord.y) }
        }
    }

    impl<T> std::ops::Index<&Coord> for Map2d<T> {
        type Output = T;

        #[inline]
        fn index(&self, coord: &Coord) -> &Self::Output {
            &self.map[coord.x * self.width + coord.y]
        }
    }

    impl<T> std::ops::IndexMut<&Coord> for Map2d<T> {
        #[inline]
        fn index_mut(&mut self, coord: &Coord) -> &mut Self::Output {
            &mut self.map[coord.x * self.width + coord.y]
        }
    }

    impl<T> std::ops::Index<usize> for Map2d<T> {
        type Output = T;

        #[inline]
        fn index(&self, p: usize) -> &Self::Output {
            &self.map[p]
        }
    }

    impl<T> std::ops::IndexMut<usize> for Map2d<T> {
        #[inline]
        fn index_mut(&mut self, p: usize) -> &mut Self::Output {
            &mut self.map[p]
        }
    }
}

}
mod problem {use super::*;

type ScoreType = f64;

#[derive(Debug, Clone)]
pub struct State {
    pub score: ScoreType,
    pub penalty: ScoreType,
    pub cards: Vec<Card>,
    pub rireki: Vec<Vec<(usize, Card)>>, // [i]: i個目のカードがmergeされたもう一方のカードのindexとmergeされるのカード
    pub cnt: usize,
}
impl State {
    pub fn new(input: &Input) -> Self {
        Self {
            score: 0.0,
            penalty: 0.0,
            cards: input.cards.clone(),
            rireki: vec![vec![]; input.n],
            cnt: 0,
        }
    }

    pub fn calc_score(&self) -> ScoreType {
        let diff_a = self.cards[0].a.abs_diff(W);
        let diff_b = self.cards[0].b.abs_diff(W);
        let diff = max(diff_a, diff_b);
        if self.cnt < 50 && false {
            // 0か0とiをmergeしたときのスコアを返す
            let mut ret = diff;
            for i in 1..self.cards.len() {
                let next_a = (self.cards[0].a + self.cards[i].a) / 2;
                let next_b = (self.cards[0].b + self.cards[i].b) / 2;
                let diff_a = next_a.abs_diff(W);
                let diff_b = next_b.abs_diff(W);
                let diff = max(diff_a, diff_b);
                ret = ret.min(diff);
            }
            return (ret as f64 + 1.0).log10();
        }
        (diff as f64 + 1.0).log10()
    }

    pub fn apply(&mut self, action: (usize, usize)) {
        self.rireki[action.0].push((action.1, self.cards[action.0]));
        self.rireki[action.1].push((action.0, self.cards[action.1]));

        let next_a = (self.cards[action.0].a + self.cards[action.1].a) / 2;
        let next_b = (self.cards[action.0].b + self.cards[action.1].b) / 2;
        self.cards[action.0].a = next_a;
        self.cards[action.0].b = next_b;
        self.cards[action.1].a = next_a;
        self.cards[action.1].b = next_b;
        self.score = self.calc_score();
        self.cnt += 1;
        self.penalty = (self.cnt as f64 - 50.0).max(0.0);
    }

    pub fn revert(&mut self, action: (usize, usize)) {
        assert!(self.rireki[action.0].len() > 0);
        assert!(self.rireki[action.1].len() > 0);
        let aa = self.rireki[action.0].len();
        self.cards[action.0] = self.rireki[action.0].last().unwrap().1;
        self.cards[action.1] = self.rireki[action.1].last().unwrap().1;
        self.rireki[action.0].pop();
        self.rireki[action.1].pop();
        assert!(self.rireki[action.0].len() == aa - 1);
        self.score = self.calc_score();
        self.cnt -= 1;
        self.penalty = (self.cnt as f64 - 50.0).max(0.0);
    }

    pub fn to_output(&mut self, input: &Input) -> Output {
        let mut actions = vec![];
        while self.rireki.iter().any(|x| !x.is_empty()) {
            let u = rnd::get(input.n);
            if self.rireki[u].is_empty() {
                continue;
            }
            let v = self.rireki[u].last().unwrap().0;
            if self.rireki[v].last().unwrap().0 != u {
                continue;
            }
            actions.push((u, v));
            self.rireki[u].pop();
            self.rireki[v].pop();
        }
        Output {
            score: self.score,
            actions,
        }
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Card {
    a: usize,
    b: usize,
}
impl Card {
    fn new(a: usize, b: usize) -> Self {
        Self { a, b }
    }
}

pub struct Input {
    pub n: usize,
    pub cards: Vec<Card>,
}
pub fn read_input() -> Input {
    let n = input_1::<usize>();
    let mut cards = vec![];
    for _ in 0..n {
        let v = input_vec1::<usize>();
        cards.push(Card::new(v[0], v[1]));
    }
    Input { n, cards }
}

pub struct Output {
    pub score: ScoreType,
    pub actions: Vec<(usize, usize)>,
}
impl Output {
    pub fn print_ans(&self) {
        let score = 2e6 - 1e5 * self.score;
        crate::printdata!(score);
        assert!(self.actions.len() <= 50);
        println!("{}", self.actions.len());
        for &(a, b) in self.actions.iter() {
            assert!(a != b);
            println!("{} {}", a + 1, b + 1);
        }
    }
}

fn input_1<T: std::str::FromStr>() -> T
where
    <T as std::str::FromStr>::Err: core::fmt::Debug,
{
    let mut a = String::new();
    std::io::stdin().read_line(&mut a).unwrap();
    a.trim().parse().unwrap()
}

fn input_vec1<T: std::str::FromStr>() -> Vec<T> {
    let mut a = String::new();
    std::io::stdin().read_line(&mut a).unwrap();
    a.trim()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}


}
mod sa {use super::*;

type ScoreType = f64;

pub struct SASolver {
    start_time: f64,
    duration: f64,
    temp: f64,
    log_table: [f64; 65536],
    pub state: State,
    best_state: State,
    time: f64,
    mae_kousin_best: f64,
    regal_iter: usize,
}

impl SASolver {
    const GOAL: OptimizationGoal = OptimizationGoal::Min;
    const START_TEMP: f64 = 2.00;
    const END_TEMP: f64 = 0.1;
    const DIFF_TEMP: f64 = Self::END_TEMP / Self::START_TEMP;

    pub fn new(state: State) -> Self {
        let mut log_table = [0.0; 65536];
        for i in 0..65536 {
            log_table[i] = ((i as f64 + 0.5) / 65536.0).ln();
        }
        rnd::shuffle(&mut log_table);

        Self {
            start_time: 0.0,
            duration: 0.0,
            temp: 0.0,
            log_table,
            state: state.clone(),
            best_state: state.clone(),
            time: 0.0,
            mae_kousin_best: 0.0,
            regal_iter: 0,
        }
    }

    fn update(&mut self) -> bool {
        self.time = get_time();
        if self.time - self.start_time > self.duration {
            return false;
        }
        // 非線形
        //self.temp =
        //  Self::START_TEMP * Self::DIFF_TEMP.powf((self.time - self.start_time) / self.duration);
        // 線形
        //self.temp = Self::START_TEMP
        //    + (Self::END_TEMP - Self::START_TEMP) * (get_time() - self.start_time) / self.duration;
        //
        self.temp = Self::START_TEMP
            * Self::DIFF_TEMP.powf(((self.time - self.start_time) / self.duration).powf(1.5));
        true
    }

    fn select_neighborhood(&mut self, input: &Input, _iter: usize) -> Box<dyn Neighbor> {
        const CNT_NEIGHBORHOOD: usize = 2;
        static neighborhood_ratio: [usize; CNT_NEIGHBORHOOD] = [50, 100];
        let op = rnd::get(100);

        if op < neighborhood_ratio[0] {
            Box::new(neighborhood::Apply::new(input, &self.state))
        } else {
            Box::new(neighborhood::Revert::new(input, &self.state))
        }
    }

    fn update_best_state(&mut self) -> bool {
        if self.state.cnt > 50 {
            return false;
        }
        if Self::GOAL == OptimizationGoal::Max {
            if self.state.score > self.best_state.score {
                self.best_state = self.state.clone();
                self.mae_kousin_best = self.time;
                return true;
            }
        } else {
            if self.state.score < self.best_state.score {
                self.best_state = self.state.clone();
                self.mae_kousin_best = self.time;
                return true;
            }
        }
        false
    }

    fn is_accepted(
        &mut self,
        _input: &Input,
        pre_score: (ScoreType, ScoreType),
        next_score: (ScoreType, ScoreType),
        iter_sa: usize,
    ) -> bool {
        self.regal_iter += 1;
        let ss = 0.1;
        let pre_score = pre_score.0 as f64
            + ss * pre_score.1 as f64 * (self.time - self.start_time) / self.duration as f64;
        let next_score = next_score.0 as f64
            + ss * next_score.1 as f64 * (self.time - self.start_time) / self.duration as f64;
        if Self::GOAL == OptimizationGoal::Max {
            next_score as f64 - pre_score as f64
                >= self.temp as f64 * self.log_table[iter_sa & 65535] as f64
        } else {
            -(next_score as f64 - pre_score as f64)
                >= self.temp as f64 * self.log_table[iter_sa & 65535] as f64
        }
    }

    pub fn run(&mut self, input: &Input, duration: f64) {
        self.start_time = get_time();
        self.duration = duration;

        let mut iter_sa = 0;
        let mut cnt_ac = 0;
        let mut cnt_upd_best = 0;
        while iter_sa & 127 != 0 || self.update() {
            iter_sa += 1;
            let pre_score = (self.state.score, self.state.penalty);
            let neighbor: Box<dyn Neighbor> = self.select_neighborhood(input, iter_sa);

            if neighbor.preprocess(input, &mut self.state)
                && self.is_accepted(
                    input,
                    pre_score,
                    (self.state.score, self.state.penalty),
                    iter_sa,
                )
            {
                neighbor.postprocess(input, &mut self.state);
                if self.update_best_state() {
                    cnt_upd_best += 1;
                }
                cnt_ac += 1;
            } else {
                neighbor.rollback(input, &mut self.state, pre_score);
            }
        }
        crate::printdata!(iter_sa);
        eprintln!("regal_iter: {}", self.regal_iter);
        eprintln!("cnt_ac: {}", cnt_ac);
        eprintln!("cnt_upd_best: {}", cnt_upd_best);
        eprintln!("mae_kousin_best: {}", self.mae_kousin_best);
        self.state = self.best_state.clone();
    }
}

#[derive(PartialEq)]
enum OptimizationGoal {
    Max,
    Min,
}
trait Neighbor {
    fn preprocess(&self, input: &Input, state: &mut State) -> bool;
    fn postprocess(&self, input: &Input, state: &mut State);
    fn rollback(&self, input: &Input, state: &mut State, pre_score: (ScoreType, ScoreType));
}

mod neighborhood {
    use super::*;
    pub struct Apply {
        action: (usize, usize),
    }
    impl Apply {
        pub fn new(input: &Input, _state: &State) -> Self {
            let u = rnd::get(input.n);
            let v = rnd::range_skip(0, input.n, u);
            assert!(u != v);
            Self { action: (u, v) }
        }
    }
    impl Neighbor for Apply {
        fn preprocess(&self, _input: &Input, state: &mut State) -> bool {
            state.apply(self.action);
            true
        }
        fn postprocess(&self, _input: &Input, _state: &mut State) {}
        fn rollback(&self, _input: &Input, state: &mut State, _pre_score: (ScoreType, ScoreType)) {
            state.revert(self.action);
        }
    }

    pub struct Revert {
        action: (usize, usize),
    }
    impl Revert {
        pub fn new(input: &Input, state: &State) -> Self {
            if state.penalty < 1e-9 {
                return Self { action: (!0, !0) };
            }
            loop {
                let u = rnd::get(input.n);
                if state.rireki[u].len() == 0 {
                    continue;
                }
                let v = state.rireki[u].last().unwrap().0;
                if u != state.rireki[v].last().unwrap().0 {
                    continue;
                }

                return Self { action: (u, v) };
            }
        }
    }
    impl Neighbor for Revert {
        fn preprocess(&self, _input: &Input, state: &mut State) -> bool {
            if self.action == (!0, !0) {
                return false;
            }
            state.revert(self.action);
            true
        }
        fn postprocess(&self, _input: &Input, _state: &mut State) {}
        fn rollback(&self, _input: &Input, state: &mut State, _pre_score: (ScoreType, ScoreType)) {
            if self.action == (!0, !0) {
                return;
            }
            state.apply(self.action);
        }
    }
}

}

mod utils {use super::*;


#[macro_export]
macro_rules! printdata {
    ( $($x:expr),* ) => {{
        $(eprintln!("[DATA] {} = {:?}", stringify!($x), $x);)*
    }}
}

pub mod rnd {
    static mut A: u64 = 1;

    pub fn next() -> u32 {
        unsafe {
            let mut x = A;
            A *= 0xcafef00dd15ea5e5;
            x ^= x >> 22;
            (x >> 22 + (x >> 61)) as u32
        }
    }

    pub fn next64() -> u64 {
        (next() as u64) << 32 | next() as u64
    }

    pub fn nextf() -> f64 {
        unsafe { std::mem::transmute::<u64, f64>(0x3ff0000000000000 | (next() as u64) << 20) - 1. }
    }

    pub fn get(n: usize) -> usize {
        assert!(n <= u32::MAX as usize);
        next() as usize * n >> 32
    }

    pub fn range(a: usize, b: usize) -> usize {
        assert!(a < b);
        get(b - a) + a
    }

    pub fn range_skip(a: usize, b: usize, skip: usize) -> usize {
        assert!(a <= skip && skip < b);
        let n = range(a, b - 1);
        n + (skip <= n) as usize
    }

    pub fn rangei(a: i64, b: i64) -> i64 {
        assert!(a < b);
        get((b - a) as usize) as i64 + a
    }

    pub fn shuffle<T>(list: &mut [T]) {
        for i in (0..list.len()).rev() {
            list.swap(i, get(i + 1));
        }
    }

    pub fn shuffle_iter<T: Copy>(list: &mut [T]) -> impl Iterator<Item = T> + '_ {
        (0..list.len()).rev().map(|i| {
            list.swap(i, get(i + 1));
            list[i]
        })
    }
}

pub trait RandomChoice {
    type Output;
    fn choice(&self) -> Self::Output;
}
impl<T: Copy> RandomChoice for [T] {
    type Output = T;
    fn choice(&self) -> T {
        self[rnd::get(self.len())]
    }
}

pub fn get_time() -> f64 {
    static mut START: f64 = -1.0;
    let end = std::time::SystemTime::now()
        .duration_since(std::time::UNIX_EPOCH)
        .unwrap()
        .as_secs_f64();
    unsafe {
        if START < 0.0 {
            START = end;
        }
        end - START
    }
}

}