#783381 (Rust) No.5007 Steiner Space Travel

• 問題: No.5007 Steiner Space Travel
• ユーザー: shamio
• 提出日時: 2022-07-30 17:52:56
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 992 ms / 1,000 ms
• コード長: 19,390 bytes
• コンパイル時間: 1,266 ms
• 実行使用メモリ: 6,952 KB
• スコア: 8,791,173
• 最終ジャッジ日時: 2022-07-30 17:53:39
• 合計ジャッジ時間: 33,791 ms
• ジャッジサーバーID （参考情報）: judge15 / judge9

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	991 ms; 4,904 KB
testcase_01	AC	991 ms; 4,900 KB
testcase_02	AC	992 ms; 4,904 KB
testcase_03	AC	991 ms; 4,908 KB
testcase_04	AC	991 ms; 4,904 KB
testcase_05	AC	991 ms; 4,900 KB
testcase_06	AC	991 ms; 4,900 KB
testcase_07	AC	991 ms; 6,952 KB
testcase_08	AC	992 ms; 4,904 KB
testcase_09	AC	991 ms; 6,952 KB
testcase_10	AC	991 ms; 6,952 KB
testcase_11	AC	991 ms; 6,952 KB
testcase_12	AC	991 ms; 4,900 KB
testcase_13	AC	991 ms; 4,904 KB
testcase_14	AC	991 ms; 6,952 KB
testcase_15	AC	991 ms; 4,904 KB
testcase_16	AC	991 ms; 4,904 KB
testcase_17	AC	991 ms; 4,904 KB
testcase_18	AC	990 ms; 4,904 KB
testcase_19	AC	991 ms; 4,908 KB
testcase_20	AC	991 ms; 6,948 KB
testcase_21	AC	991 ms; 6,948 KB
testcase_22	AC	992 ms; 4,904 KB
testcase_23	AC	991 ms; 6,948 KB
testcase_24	AC	991 ms; 6,948 KB
testcase_25	AC	991 ms; 6,948 KB
testcase_26	AC	991 ms; 4,900 KB
testcase_27	AC	990 ms; 4,904 KB
testcase_28	AC	991 ms; 4,900 KB
testcase_29	AC	990 ms; 4,900 KB

コンパイルメッセージ

warning: unnecessary parentheses around method argument
   --> Main.rs:178:35
    |
178 |             let j = i + self.next((a.len() - i)) as usize;
    |                                   ^           ^
    |
    = note: `#[warn(unused_parens)]` on by default
help: remove these parentheses
    |
178 -             let j = i + self.next((a.len() - i)) as usize;
178 +             let j = i + self.next(a.len() - i) as usize;
    | 

warning: unused variable: `energies`
   --> Main.rs:238:5
    |
238 |     energies: &[[i32; NUM_COMMETS]; NUM_COMMETS],
    |     ^^^^^^^^ help: if this is intentional, prefix it with an underscore: `_energies`
    |
    = note: `#[warn(unused_variables)]` on by default

warning: unused variable: `neighbor_percentages`
   --> Main.rs:376:9
    |
376 |     let neighbor_percentages = [10, 10, 10, 70];
    |         ^^^^^^^^^^^^^^^^^^^^ help: if this is intentional, prefix it with an underscore: `_neighbor_percentages`

warning: variable `si` is assigned to, but never used
   --> Main.rs:500:21
    |
500 |             let mut si = 0;
    |                     ^^
    |
    = note: consider using `_si` instead

warning: variable `ci` is assigned to, but never used
   --> Main.rs:501:21
    |
501 |             let mut ci = 0;
    |                     ^^
    |
    = note: consider using `_ci` instead

warning: value assigned to `si` is never read
   --> Main.rs:504:21
    |
504 |                     si = ssi;
    |                     ^^
    |
    = note: `#[warn(unused_assignments)]` on by default
    = help: maybe it is overwritten before being read?

warning: value assigned to `ci` is never read
   --> Main.rs:505:21
    |
505 |                     ci = idx;
    |                     ^^
    |
    = help: maybe it is overwritten before being read?

warning: unused variable: `score`
   --> Main.rs:598:9
    |
598 |     let score = (1_000_000_000.0 / (1000.0 + (best_sum_energies as f64).sqrt())).round() as i32;
    |         ^^^^^ help: if this is

ソースコード

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        #[cfg(feature = "single_testcase")]
        {
            eprint!("[line:{}] ", line!());
            eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
        }
    }
}

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;
        }
        ms - STIME
    }
}

//--------------------------------------------------------------------------------
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8#%E8%BF%BD%E8%A8%98-%E9%81%85%E5%BB%B6%E5%85%A5%E5%8A%9B

#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

//--------------------------------------------------------------------------------
// https://atcoder.jp/contests/intro-heuristics/submissions/14832097

#[allow(dead_code)]
fn readln() -> String {
    let mut line = String::new();
    ::std::io::stdin()
        .read_line(&mut line)
        .unwrap_or_else(|e| panic!("{}", e));
    line
}

#[allow(unused_macros)]
macro_rules! read {
	($($t:tt),*; $n:expr) => {{
		let stdin = ::std::io::stdin();
		let ret = ::std::io::BufRead::lines(stdin.lock()).take($n).map(|line| {
			let line = line.unwrap();
			let mut it = line.split_whitespace();
			_read!(it; $($t),*)
		}).collect::<Vec<_>>();
		ret
	}};
	($($t:tt),*) => {{
		let line = readln();
		let mut it = line.split_whitespace();
		_read!(it; $($t),*)
	}};
}

macro_rules! _read {
	($it:ident; [char]) => {
		_read!($it; String).chars().collect::<Vec<_>>()
	};
	($it:ident; [u8]) => {
		Vec::from(_read!($it; String).into_bytes())
	};
	($it:ident; usize1) => {
		$it.next().unwrap_or_else(|| panic!("input mismatch")).parse::<usize>().unwrap_or_else(|e| panic!("{}", e)) - 1
	};
	($it:ident; [usize1]) => {
		$it.map(|s| s.parse::<usize>().unwrap_or_else(|e| panic!("{}", e)) - 1).collect::<Vec<_>>()
	};
	($it:ident; [$t:ty]) => {
		$it.map(|s| s.parse::<$t>().unwrap_or_else(|e| panic!("{}", e))).collect::<Vec<_>>()
	};
	($it:ident; $t:ty) => {
		$it.next().unwrap_or_else(|| panic!("input mismatch")).parse::<$t>().unwrap_or_else(|e| panic!("{}", e))
	};
	($it:ident; $($t:tt),+) => {
		($(_read!($it; $t)),*)
	};
}

//--------------------------------------------------------------------------------
// https://atcoder.jp/contests/hokudai-hitachi2017-1/submissions/1797182
// u32 -> usize

pub struct XorShift {
    pub x: [usize; 4],
}

impl XorShift {
    pub fn new(mut seed: usize) -> XorShift {
        let mut x = [0; 4];
        for i in 0..4 {
            seed = 1812433253usize
                .wrapping_mul(seed ^ (seed >> 30))
                .wrapping_add(i as usize);
            x[i] = seed;
        }
        XorShift { x: x }
    }
    pub fn next_usize(&mut self) -> usize {
        let t = self.x[0] ^ (self.x[0] << 11);
        for i in 0..3 {
            self.x[i] = self.x[i + 1]
        }
        self.x[3] = self.x[3] ^ (self.x[3] >> 19) ^ t ^ (t >> 8);
        self.x[3]
    }
    /// [0, n)
    pub fn next(&mut self, n: usize) -> usize {
        loop {
            let t = self.next_usize();
            let r = t % n;
            if (t - r).checked_add(n).is_some() {
                return r;
            }
        }
    }
    pub fn shuffle<T>(&mut self, a: &mut [T]) {
        for i in 0..a.len() {
            let j = i + self.next((a.len() - i)) as usize;
            a.swap(i, j);
        }
    }
}

//--------------------------------------------------------------------------------

const SEED: u32 = 890482;
const TIME_LIMIT: f64 = 0.99;
const INF: usize = 1_000_000_000;
const INF_F64: f64 = 1_000_000_000.0;

const D: [(i32, i32); 4] = [(1, 0), (0, 1), (-1, 0), (0, -1)];

const NUM_COMMETS: usize = 100;
const NUM_STATIONS: usize = 8;
const ALPHA: i32 = 5;
const ALPHAS: [i32; 3] = [ALPHA * ALPHA, ALPHA, 1];

#[allow(dead_code)]
fn sample_output() {
    for _ in 0..NUM_STATIONS {
        eprintln!("{} {}", 0, 0);
        println!("{} {}", 0, 0);
    }

    let v = NUM_COMMETS + 1;
    eprintln!("{}", v);
    println!("{}", v);
    for i in 0..NUM_COMMETS {
        eprintln!("{} {}", 1, i + 1);
        println!("{} {}", 1, i + 1);
    }
    eprintln!("{} {}", 1, 1);
    println!("{} {}", 1, 1);
}

fn get_energy(x_from: i32, y_from: i32, x_to: i32, y_to: i32, which: usize) -> i32 {
    ((x_from - x_to) * (x_from - x_to) + (y_from - y_to) * (y_from - y_to)) * ALPHAS[which]
}

fn print_output(stations: &[(i32, i32)], route: &[usize]) {
    for &(x, y) in stations.iter() {
        println!("{} {}", x, y);
    }
    println!("{}", route.len());
    for &i in route.iter() {
        if i < NUM_COMMETS {
            println!("{} {}", 1, i + 1);
        } else {
            println!("{} {}", 2, i + 1 - NUM_COMMETS);
        }
    }
}

fn compute_sum_energies_all(
    route: &[usize],
    stations: &[(i32, i32)],
    commets: &[(i32, i32)],
    energies: &[[i32; NUM_COMMETS]; NUM_COMMETS],
) -> i32 {
    let mut sum_energies = 0;
    for i in 0..route.len() - 1 {
        let from = route[i];
        let to = route[i + 1];
        let bl_from = from < NUM_COMMETS;
        let bl_to = to < NUM_COMMETS;
        let which = if bl_from && bl_to {
            0
        } else if bl_from || bl_to {
            1
        } else {
            2
        };
        let (x_from, y_from) = if bl_from {
            commets[from]
        } else {
            stations[from - NUM_COMMETS]
        };
        let (x_to, y_to) = if bl_to {
            commets[to]
        } else {
            stations[to - NUM_COMMETS]
        };

        let energy = get_energy(x_from, y_from, x_to, y_to, which);
        sum_energies += energy;
    }

    sum_energies
}

fn is_station(i: usize) -> bool {
    i >= NUM_COMMETS
}

fn compute_station_energies(
    commets_arround_station: &[(usize, usize)],
    station: (i32, i32),
    commets: &[(i32, i32)],
) -> i32 {
    let (x_station, y_station) = station;
    let mut sum_energies = 0;
    for &(u, v) in commets_arround_station.iter() {
        let (xu, yu) = commets[u];
        sum_energies += get_energy(xu, yu, x_station, y_station, 1);
        let (xv, yv) = commets[v];
        sum_energies += get_energy(x_station, y_station, xv, yv, 1);
    }
    sum_energies
}

fn compute_best_station(
    commets_arround_station: &[(usize, usize)],
    commets: &[(i32, i32)],
) -> (i32, i32) {
    let mut x_sum = 0;
    let mut y_sum = 0;
    for &(u, v) in commets_arround_station.iter() {
        let (xu, yu) = commets[u];
        x_sum += xu;
        y_sum += yu;
        let (xv, yv) = commets[v];
        x_sum += xv;
        y_sum += yv;
    }
    let mut x_station = (x_sum as f64 / (2.0 * commets_arround_station.len() as f64)) as i32;
    let mut y_station = (y_sum as f64 / (2.0 * commets_arround_station.len() as f64)) as i32;

    // let mut sum_energies =
    //     compute_station_energies(commets_arround_station, (x_station, y_station), commets);
    // for i in 0..1000 {
    //     let mut best_di = None;
    //     for (di, &(dx, dy)) in D.iter().enumerate() {
    //         let next_x_station = x_station + dx;
    //         let next_y_station = y_station + dy;
    //         let next_sum_energies = compute_station_energies(
    //             commets_arround_station,
    //             (next_x_station, next_y_station),
    //             commets,
    //         );
    //         if next_sum_energies <= sum_energies {
    //             best_di = Some(di);
    //             sum_energies = next_sum_energies;
    //         }
    //     }

    //     match best_di {
    //         Some(best_di) => {
    //             let (dx, dy) = D[best_di];
    //             x_station += dx;
    //             y_station += dy;
    //         }
    //         None => {
    //             break;
    //         }
    //     }
    // }

    (x_station, y_station)
}

fn main() {
    get_time();

    let mut xorshift = XorShift::new(SEED as usize);

    let (_n, _m) = read!(usize, usize);

    let mut commets = Vec::with_capacity(NUM_COMMETS);
    for _ in 0..NUM_COMMETS {
        let (x, y) = read!(i32, i32);
        commets.push((x, y));
    }

    let mut energies = [[0; NUM_COMMETS]; NUM_COMMETS];
    for (i, &(xi, yi)) in commets.iter().enumerate() {
        for (j, &(xj, yj)) in commets.iter().enumerate() {
            let energy = get_energy(xi, yi, xj, yj, 0);
            energies[i][j] = energy;
        }
    }

    let mut stations = [(0, 0); NUM_STATIONS];
    for i in 0..NUM_STATIONS {
        let x = xorshift.next(1000) as i32;
        let y = xorshift.next(1000) as i32;
        stations[i] = (x, y);
    }
    let mut commets_arround_stations = vec![vec![]; NUM_STATIONS];
    let mut route: Vec<usize> = (1..NUM_COMMETS).collect();
    xorshift.shuffle(&mut route);
    route.insert(0, 0);
    route.push(0);
    let mut sum_energies: i32 = compute_sum_energies_all(&route, &stations, &commets, &energies);

    const NUM_NEIGHBORS: usize = 4;
    let neighbor_percentages = [10, 10, 10, 70];
    let neighbor_percentages = [10, 10, 0, 80];
    // let neighbor_percentages = [100, 0, 0, 0];
    // let neighbor_percentages = [0, 0, 0, 100];

    let mut accumulate_percentages = [0; NUM_NEIGHBORS];
    let mut acc = 0;
    for (i, &e) in neighbor_percentages.iter().enumerate() {
        acc += e;
        accumulate_percentages[i] = acc;
    }
    assert_eq!(accumulate_percentages[NUM_NEIGHBORS - 1], 100);

    const TEMP_START: f64 = 1000000.0;
    const TEMP_END: f64 = 100.0;
    let mut temp = TEMP_START;
    let mut best_route = route.clone();
    let mut best_stations = stations.clone();
    let mut best_sum_energies = sum_energies;
    for cnt in 1.. {
        if cnt % 128 == 0 {
            let t = get_time() / TIME_LIMIT;
            if t >= 1.0 {
                debug!(cnt);
                break;
            }
            temp = TEMP_START.powf(1.0 - t) * TEMP_END.powf(t);
        }

        let which_neighbor = xorshift.next(100);
        if which_neighbor < accumulate_percentages[0] {
            // insert station
            // u(i) -> s -> v(i + 1)
            let i = xorshift.next(route.len() - 1);
            let u = route[i];
            let v = route[i + 1];
            if is_station(u) || is_station(v) {
                continue;
            }
            let (xu, yu) = commets[u];
            let (xv, yv) = commets[v];
            let si = xorshift.next(NUM_STATIONS);
            let mut next_sum_energies = sum_energies;
            next_sum_energies -=
                compute_station_energies(&commets_arround_stations[si], stations[si], &commets);
            next_sum_energies -= get_energy(xu, yu, xv, yv, 0);
            commets_arround_stations[si].push((u, v));
            let next_station = compute_best_station(&commets_arround_stations[si], &commets);
            next_sum_energies +=
                compute_station_energies(&commets_arround_stations[si], next_station, &commets);
            let diff = sum_energies - next_sum_energies;
            if diff >= 0 || f64::exp(diff as f64 / temp) * INF_F64 >= xorshift.next(INF) as f64 {
                stations[si] = next_station;
                sum_energies = next_sum_energies;
                route.insert(i + 1, si + NUM_COMMETS);
                if sum_energies < best_sum_energies {
                    best_sum_energies = sum_energies;
                    best_route = route.clone();
                    best_stations = stations.clone();
                }
            } else {
                commets_arround_stations[si].pop();
            }
        } else if which_neighbor < accumulate_percentages[1] {
            // delete station
            let mut sum_stations = 0;
            for v in commets_arround_stations.iter() {
                sum_stations += v.len();
            }
            if sum_stations == 0 {
                continue;
            }
            let mut idx = xorshift.next(sum_stations);
            let mut si = 0;
            let mut ci = 0;
            for (ssi, v) in commets_arround_stations.iter().enumerate() {
                if idx < v.len() {
                    si = ssi;
                    ci = idx;
                    break;
                } else {
                    idx -= v.len();
                }
            }
            let mut next_sum_energies = sum_energies;
            next_sum_energies -=
                compute_station_energies(&commets_arround_stations[si], stations[si], &commets);
            let (u, v) = commets_arround_stations[si].swap_remove(ci);
            let (xu, yu) = commets[u];
            let (xv, yv) = commets[v];
            next_sum_energies +=
                compute_station_energies(&commets_arround_stations[si], stations[si], &commets);
            next_sum_energies += get_energy(xu, yu, xv, yv, 0);
            let diff = sum_energies - next_sum_energies;
            if diff >= 0 || f64::exp(diff as f64 / temp) * INF_F64 >= xorshift.next(INF) as f64 {
                sum_energies = next_sum_energies;
                let mut idx = 0;
                for i in 1..route.len() - 1 {
                    let uu = route[i - 1];
                    let vv = route[i + 1];
                    if uu == u && vv == v {
                        idx = i;
                        break;
                    }
                }
                route.remove(idx);
                if sum_energies < best_sum_energies {
                    best_sum_energies = sum_energies;
                    best_route = route.clone();
                    best_stations = stations.clone();
                }
            } else {
                commets_arround_stations[si].push((u, v));
            }
        } else if which_neighbor < accumulate_percentages[2] {
            // move station
            let mut sum_stations = 0;
            for v in commets_arround_stations.iter() {
                sum_stations += v.len();
            }
            if sum_stations == 0 {
                continue;
            }
            let mut idx = xorshift.next(sum_stations);
            let mut si = 0;
            let mut ci = 0;
            for (ssi, v) in commets_arround_stations.iter().enumerate() {
                if idx < v.len() {
                    si = ssi;
                    ci = idx;
                    break;
                } else {
                    idx -= v.len();
                }
            }
        } else {
            let mut i = xorshift.next(route.len() - 1);
            let mut j = xorshift.next(route.len() - 1);
            if i == j {
                continue;
            }
            if i > j {
                std::mem::swap(&mut i, &mut j);
            }

            let mut next_sum_energies = sum_energies;
            let i_from = route[i];
            let i_to = route[i + 1];
            let j_from = route[j];
            let j_to = route[j + 1];
            if is_station(i_from) && is_station(j_from) || is_station(i_to) && is_station(j_to) {
                continue;
            }
            let (xi_from, yi_from) = if is_station(i_from) {
                stations[i_from - NUM_COMMETS]
            } else {
                commets[i_from]
            };
            let (xi_to, yi_to) = if is_station(i_to) {
                stations[i_to - NUM_COMMETS]
            } else {
                commets[i_to]
            };
            let (xj_from, yj_from) = if is_station(j_from) {
                stations[j_from - NUM_COMMETS]
            } else {
                commets[j_from]
            };
            let (xj_to, yj_to) = if is_station(j_to) {
                stations[j_to - NUM_COMMETS]
            } else {
                commets[j_to]
            };
            let which = if is_station(i_from) || is_station(i_to) {
                1
            } else {
                0
            };
            next_sum_energies -= get_energy(xi_from, yi_from, xi_to, yi_to, which);
            let which = if is_station(j_from) || is_station(j_to) {
                1
            } else {
                0
            };
            next_sum_energies -= get_energy(xj_from, yj_from, xj_to, yj_to, which);
            let which = if is_station(i_from) || is_station(j_from) {
                1
            } else {
                0
            };
            next_sum_energies += get_energy(xi_from, yi_from, xj_from, yj_from, which);
            let which = if is_station(i_to) || is_station(j_to) {
                1
            } else {
                0
            };
            next_sum_energies += get_energy(xi_to, yi_to, xj_to, yj_to, which);
            let diff = sum_energies - next_sum_energies;
            if diff >= 0 || f64::exp(diff as f64 / temp) * INF_F64 >= xorshift.next(INF) as f64 {
                sum_energies = next_sum_energies;
                route[i + 1..=j].reverse();
                for si in 0..NUM_STATIONS {
                    commets_arround_stations[si].clear();
                }
                for idx in 1..route.len() - 1 {
                    let x = route[idx];
                    if is_station(x) {
                        let u = route[idx - 1];
                        let v = route[idx + 1];
                        let si = x - NUM_COMMETS;
                        commets_arround_stations[si].push((u, v));
                    }
                }
                if sum_energies < best_sum_energies {
                    best_sum_energies = sum_energies;
                    best_route = route.clone();
                    best_stations = stations.clone();
                }
            }
        }
    }

    let score = (1_000_000_000.0 / (1000.0 + (best_sum_energies as f64).sqrt())).round() as i32;
    debug!(score);
    print_output(&best_stations, &best_route);

    eprintln!("time_elapsed: {:.3}", get_time());
}