#955807 (Rust) No.5020 Averaging

• 問題: No.5020 Averaging
• ユーザー: hangry
• 提出日時: 2024-02-25 18:23:01
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 953 ms / 1,000 ms
• コード長: 32,976 bytes
• コンパイル時間: 1,808 ms
• コンパイル使用メモリ: 195,708 KB
• 実行使用メモリ: 6,676 KB
• スコア: 72,081,569
• 最終ジャッジ日時: 2024-02-25 18:23:53
• 合計ジャッジ時間: 52,323 ms
• ジャッジサーバーID （参考情報）: judge14 / judge13

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	952 ms; 6,676 KB
testcase_01	AC	951 ms; 6,676 KB
testcase_02	AC	951 ms; 6,676 KB
testcase_03	AC	952 ms; 6,676 KB
testcase_04	AC	952 ms; 6,676 KB
testcase_05	AC	952 ms; 6,676 KB
testcase_06	AC	951 ms; 6,676 KB
testcase_07	AC	951 ms; 6,676 KB
testcase_08	AC	951 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	951 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	951 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	951 ms; 6,676 KB
testcase_23	AC	951 ms; 6,676 KB
testcase_24	AC	952 ms; 6,676 KB
testcase_25	AC	951 ms; 6,676 KB
testcase_26	AC	951 ms; 6,676 KB
testcase_27	AC	951 ms; 6,676 KB
testcase_28	AC	951 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	951 ms; 6,676 KB
testcase_33	AC	951 ms; 6,676 KB
testcase_34	AC	951 ms; 6,676 KB
testcase_35	AC	952 ms; 6,676 KB
testcase_36	AC	952 ms; 6,676 KB
testcase_37	AC	953 ms; 6,676 KB
testcase_38	AC	951 ms; 6,676 KB
testcase_39	AC	952 ms; 6,676 KB
testcase_40	AC	952 ms; 6,676 KB
testcase_41	AC	951 ms; 6,676 KB
testcase_42	AC	952 ms; 6,676 KB
testcase_43	AC	951 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	951 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::*,
    sa2::*,
    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 = State2::new(input);
    state.score = state.calc_score(input);
    let mut solver = SASolver::new(state.clone());
    solver.run(input, TIME_LIMIT - get_time());
    let sa_score = solver.state.score;
    let len = solver.state.jun.len();
    let c0a = ((input.cards[0].a.abs_diff(W) as f64).log10() * 1000.0).round() / 1000.0;
    let c0b = ((input.cards[0].b.abs_diff(W) as f64).log10() * 1000.0).round() / 1000.0;
    crate::printdata!(sa_score, len, c0a, c0b);
    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)]
    pub struct State2 {
        pub score: ScoreType,
        pub penalty: ScoreType,
        pub jun: Vec<usize>,
    }
    impl State2 {
        pub fn new(input: &Input) -> Self {
            let mut jun = (0..input.n).rev().collect::<Vec<_>>();
            for _ in 0..0 {
                jun.insert(20, 0);
            }
            Self {
                score: 0.0,
                penalty: 0.0,
                jun,
            }
        }

        pub fn calc_score(&self, input: &Input) -> ScoreType {
            let mut cards = input.cards.clone();
            for i in 0..self.jun.len() - 1 {
                let next = merge_cards(&cards[self.jun[i]], &cards[self.jun[i + 1]]);
                cards[self.jun[i]] = next;
                cards[self.jun[i + 1]] = next;
            }
            let diff_a = cards[0].a.abs_diff(W);
            let diff_b = cards[0].b.abs_diff(W);
            let diff = max(diff_a, diff_b);
            (diff as f64 + 1.0).log10()
        }

        pub fn swap(&mut self, i: usize, j: usize) {
            self.jun.swap(i, j);
        }

        pub fn insert(&mut self, i: usize, card_idx: usize) {
            self.jun.insert(i, card_idx);
        }

        pub fn remove(&mut self, i: usize) {
            self.jun.remove(i);
        }

        pub fn to_output(&mut self, _input: &Input) -> Output {
            let mut actions = vec![];
            for i in 0..self.jun.len() - 1 {
                if self.jun[i] == self.jun[i + 1] {
                    continue;
                }
                actions.push((self.jun[i], self.jun[i + 1]));
            }
            Output {
                score: self.score,
                actions,
            }
        }
    }

    fn merge_cards(x: &Card, y: &Card) -> Card {
        Card::new((x.a + y.a) / 2, (x.b + y.b) / 2)
    }

    #[derive(Debug, Clone, Copy, PartialEq, Eq)]
    pub struct Card {
        pub a: usize,
        pub 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 sa2 {
    use super::*;

    type ScoreType = f64;

    pub struct SASolver {
        start_time: f64,
        duration: f64,
        temp: f64,
        log_table: [f64; 65536],
        pub state: State2,
        best_state: State2,
        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: State2) -> 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 Neighbor2> {
            const CNT_NEIGHBORHOOD: usize = 3;
            static neighborhood_ratio: [usize; CNT_NEIGHBORHOOD] = [100, 97, 100];
            let op = rnd::get(100);

            if op < neighborhood_ratio[0] {
                Box::new(neighborhood::Swap::new(input, &self.state))
            } else if op < neighborhood_ratio[1] {
                Box::new(neighborhood::Insert::new(input, &self.state))
            } else {
                Box::new(neighborhood::Remove::new(input, &self.state))
            }
        }

        fn update_best_state(&mut self) -> bool {
            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;
                if iter_sa & 127 == 0
                    && self.state.score > 10.0
                    && self.state.jun.len() == 45
                    && self.time - self.start_time > duration * 0.5
                {
                    self.state.insert(20, 0);
                    self.state.score = self.state.calc_score(input);
                }
                let pre_score = (self.state.score, self.state.penalty);
                let neighbor: Box<dyn Neighbor2> = 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 Neighbor2 {
        fn preprocess(&self, input: &Input, state: &mut State2) -> bool;
        fn postprocess(&self, input: &Input, state: &mut State2);
        fn rollback(&self, input: &Input, state: &mut State2, pre_score: (ScoreType, ScoreType));
    }

    mod neighborhood {
        use super::*;

        pub struct Swap {
            pub u: usize,
            pub v: usize,
        }
        impl Swap {
            pub fn new(_input: &Input, state: &State2) -> Self {
                if state.jun.len() < 3 {
                    return Self { u: !0, v: !0 };
                }
                let u = rnd::range(0, state.jun.len() - 1);
                let v = rnd::range_skip(0, state.jun.len() - 1, u);
                Self { u, v }
            }
        }
        impl Neighbor2 for Swap {
            fn preprocess(&self, input: &Input, state: &mut State2) -> bool {
                if self.u == !0 {
                    return false;
                }
                state.swap(self.u, self.v);
                state.score = state.calc_score(input);
                true
            }
            fn postprocess(&self, _input: &Input, _state: &mut State2) {
                //
            }
            fn rollback(
                &self,
                _input: &Input,
                state: &mut State2,
                pre_score: (ScoreType, ScoreType),
            ) {
                if self.u == !0 {
                    return;
                }
                state.swap(self.u, self.v);
                state.score = pre_score.0;
                state.penalty = pre_score.1;
            }
        }

        pub struct Insert {
            pub u: usize,
            pub card_idx: usize,
        }
        impl Insert {
            pub fn new(input: &Input, state: &State2) -> Self {
                if state.jun.len() > 50 {
                    return Self {
                        u: !0,
                        card_idx: !0,
                    };
                }
                loop {
                    let u = rnd::get(state.jun.len() - 1);
                    let card_idx = rnd::get(input.n);
                    if (u > 0 && state.jun[u - 1] == card_idx)
                        || (u < state.jun.len() - 1 && state.jun[u] == card_idx)
                    {
                        continue;
                    }
                    return Self { u, card_idx };
                }
            }
        }
        impl Neighbor2 for Insert {
            fn preprocess(&self, input: &Input, state: &mut State2) -> bool {
                if self.u == !0 {
                    return false;
                }
                state.jun.insert(self.u, self.card_idx);
                state.score = state.calc_score(input);
                true
            }
            fn postprocess(&self, _input: &Input, _state: &mut State2) {
                //
            }
            fn rollback(
                &self,
                _input: &Input,
                state: &mut State2,
                pre_score: (ScoreType, ScoreType),
            ) {
                if self.u == !0 {
                    return;
                }
                state.jun.remove(self.u);
                state.score = pre_score.0;
                state.penalty = pre_score.1;
            }
        }

        pub struct Remove {
            pub u: usize,
            pub card_idx: usize,
        }
        impl Remove {
            pub fn new(_input: &Input, state: &State2) -> Self {
                if state.jun.len() == 1 {
                    return Self {
                        u: !0,
                        card_idx: !0,
                    };
                }
                loop {
                    let u = rnd::get(state.jun.len());
                    let card_idx = state.jun[u];
                    if u > 0 && u < state.jun.len() - 1 && state.jun[u - 1] == state.jun[u + 1] {
                        continue;
                    }
                    return Self { u, card_idx };
                }
            }
        }
        impl Neighbor2 for Remove {
            fn preprocess(&self, input: &Input, state: &mut State2) -> bool {
                if self.u == !0 {
                    return false;
                }
                state.jun.remove(self.u);
                state.score = state.calc_score(input);
                true
            }
            fn postprocess(&self, _input: &Input, _state: &mut State2) {
                //
            }
            fn rollback(
                &self,
                _input: &Input,
                state: &mut State2,
                pre_score: (ScoreType, ScoreType),
            ) {
                if self.u == !0 {
                    return;
                }
                state.jun.insert(self.u, self.card_idx);
                state.score = pre_score.0;
                state.penalty = pre_score.1;
            }
        }
    }
}

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
        }
    }
}