#783029 (Rust) No.5007 Steiner Space Travel

• 問題: No.5007 Steiner Space Travel
• ユーザー: shamio
• 提出日時: 2022-07-30 15:50:06
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 952 ms / 1,000 ms
• コード長: 9,341 bytes
• コンパイル時間: 1,628 ms
• 実行使用メモリ: 2,100 KB
• スコア: 6,125,720
• 最終ジャッジ日時: 2022-07-30 15:50:39
• 合計ジャッジ時間: 32,555 ms
• ジャッジサーバーID （参考情報）: judge13 / judge15

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	951 ms; 1,876 KB
testcase_01	AC	951 ms; 1,940 KB
testcase_02	AC	951 ms; 1,912 KB
testcase_03	AC	950 ms; 1,892 KB
testcase_04	AC	951 ms; 2,068 KB
testcase_05	AC	951 ms; 2,064 KB
testcase_06	AC	951 ms; 2,064 KB
testcase_07	AC	951 ms; 1,948 KB
testcase_08	AC	950 ms; 1,952 KB
testcase_09	AC	951 ms; 1,884 KB
testcase_10	AC	951 ms; 2,020 KB
testcase_11	AC	951 ms; 1,988 KB
testcase_12	AC	951 ms; 1,984 KB
testcase_13	AC	952 ms; 2,016 KB
testcase_14	AC	951 ms; 2,048 KB
testcase_15	AC	950 ms; 1,864 KB
testcase_16	AC	951 ms; 1,884 KB
testcase_17	AC	951 ms; 1,956 KB
testcase_18	AC	951 ms; 2,032 KB
testcase_19	AC	951 ms; 1,948 KB
testcase_20	AC	950 ms; 2,012 KB
testcase_21	AC	951 ms; 1,956 KB
testcase_22	AC	951 ms; 2,060 KB
testcase_23	AC	951 ms; 1,884 KB
testcase_24	AC	951 ms; 1,948 KB
testcase_25	AC	951 ms; 2,100 KB
testcase_26	AC	950 ms; 1,944 KB
testcase_27	AC	951 ms; 1,988 KB
testcase_28	AC	951 ms; 2,052 KB
testcase_29	AC	951 ms; 1,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:234:5
    |
234 |     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: `score`
   --> Main.rs:329:9
    |
329 |     let score = (1_000_000_000.0 / (1000.0 + (sum_energies as f64).sqrt())).round() as i32;
    |         ^^^^^ help: if this is intentional, prefix it with an underscore: `_score`

warning: variable does not need to be mutable
   --> Main.rs:288:9
    |
288 |     let mut stations = [(0, 0); NUM_STATIONS];
    |         ----^^^^^^^^
    |         |
    |         help: remove this `mut`
    |
    = note: `#[warn(unused_mut)]` on by default

warning: 4 warnings emitted

ソースコード

#[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.95;

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 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];
    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);

    for cnt in 1.. {
        if cnt % 128 == 0 && get_time() > TIME_LIMIT {
            debug!(cnt);
            break;
        }

        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 (xi_from, yi_from) = commets[i_from];
        let i_to = route[i + 1];
        let (xi_to, yi_to) = commets[i_to];
        let j_from = route[j];
        let (xj_from, yj_from) = commets[j_from];
        let j_to = route[j + 1];
        let (xj_to, yj_to) = commets[j_to];
        next_sum_energies -= get_energy(xi_from, yi_from, xi_to, yi_to, 0);
        next_sum_energies -= get_energy(xj_from, yj_from, xj_to, yj_to, 0);
        next_sum_energies += get_energy(xi_from, yi_from, xj_from, yj_from, 0);
        next_sum_energies += get_energy(xi_to, yi_to, xj_to, yj_to, 0);
        if next_sum_energies <= sum_energies {
            sum_energies = next_sum_energies;
            route[i + 1..=j].reverse();
        }
    }

    let score = (1_000_000_000.0 / (1000.0 + (sum_energies as f64).sqrt())).round() as i32;
    debug!(score);
    print_output(&stations, &route);

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