#1188780 (Rust) No.3743 World Mapper

• 問題: No.3743 World Mapper
• ユーザー: 👑 terry_u16
• 提出日時: 2026-09-19 15:27:25
• 言語: Rust (1.97.1 + proconio + num + itertools + ACL)
• 結果: WA
• 実行時間: -
• コード長: 8,816 bytes
• コンパイル時間: 3,268 ms
• コンパイル使用メモリ: 218,208 KB
• 実行使用メモリ: 12,160 KB
• 最終ジャッジ日時: 2026-09-19 15:28:50
• 合計ジャッジ時間: 76,791 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge5_0

サブタスク	配点	結果
部分点1	10 %	AC * 4
部分点2	10 %	AC * 8 WA * 1
部分点3	10 %	AC * 8 WA * 6
部分点4	10 %	AC * 8 WA * 11
部分点5	10 %	AC * 8 WA * 16
部分点6	10 %	AC * 8 WA * 20 TLE * 1
部分点7	10 %	AC * 8 WA * 21 TLE * 5
部分点8	10 %	AC * 8 WA * 21 TLE * 10
部分点9	10 %	AC * 8 WA * 21 TLE * 10 -- * 5
満点	10 %	AC * 8 WA * 21 TLE * 10 -- * 10
合計	5 * 10% = 50 点

ソースコード

use std::{collections::HashSet, time::Instant};

use itertools::Itertools;
#[allow(unused_imports)]
use proconio::*;

use crate::{rand::Xoshiro256PlusPlus, util::ChangeMinMax};

fn main() {
    input! {
        n: usize,
    }

    let since = Instant::now();

    let mut rng = Xoshiro256PlusPlus::new(42);

    while since.elapsed().as_secs_f64() < 1.8 {
        let mut v: Vec<Vec<u32>> = vec![vec![0; n]; n - 1];
        let mut h: Vec<Vec<u32>> = vec![vec![0; n - 1]; n];

        for row in 0..n - 1 {
            for col in 0..n {
                v[row][col] = rng.gen_range(1..300001) as u32;
            }
        }

        for row in 0..n {
            for col in 0..n - 1 {
                h[row][col] = rng.gen_range(1..300001) as u32;
            }
        }

        if check(n, &v, &h) {
            for row in 0..n - 1 {
                println!("{}", v[row].iter().join(" "));
            }

            for row in 0..n {
                println!("{}", h[row].iter().join(" "));
            }

            return;
        }
    }

    println!("-1");
}

fn check(n: usize, v: &Vec<Vec<u32>>, h: &Vec<Vec<u32>>) -> bool {
    let mut dists = vec![vec![u32::MAX / 2; n * n]; n * n];

    for i in 0..n * n {
        dists[i][i] = 0;
    }

    for row in 0..n - 1 {
        for col in 0..n {
            let i = row * n + col;
            let j = (row + 1) * n + col;
            dists[i][j] = v[row][col];
            dists[j][i] = v[row][col];
        }
    }

    for row in 0..n {
        for col in 0..n - 1 {
            let i = row * n + col;
            let j = row * n + col + 1;
            dists[i][j] = h[row][col];
            dists[j][i] = h[row][col];
        }
    }

    for k in 0..n * n {
        for i in 0..n * n {
            for j in 0..n * n {
                let d = dists[i][k] + dists[k][j];
                dists[i][j].change_min(d);
            }
        }
    }

    let mut set = HashSet::new();

    for u in 0..n * n {
        for v in u + 1..n * n {
            if !set.insert(dists[u][v]) {
                return false;
            }
        }
    }

    true
}

#[allow(dead_code)]
mod rand {
    pub struct Xoshiro256PlusPlus {
        state: [u64; 4],
    }

    impl Xoshiro256PlusPlus {
        pub fn new(seed: u64) -> Self {
            let mut rng = Self { state: [0; 4] };
            // シードから初期状態を生成
            rng.state[0] = seed;
            rng.state[1] = seed.wrapping_mul(0x9e3779b97f4a7c15);
            rng.state[2] = seed.wrapping_mul(0xbf58476d1ce4e5b9);
            rng.state[3] = seed.wrapping_mul(0x94d049bb133111eb);

            // 初期化のために数回回す
            for _ in 0..16 {
                rng.next();
            }

            rng
        }

        pub fn from_entropy() -> Self {
            // 簡易的なエントロピー生成（実際の環境では改善が必要）
            let seed = std::ptr::null::<u8>() as usize as u64;
            Self::new(seed)
        }

        pub fn next(&mut self) -> u64 {
            let result = self.state[0]
                .wrapping_add(self.state[3])
                .rotate_left(23)
                .wrapping_add(self.state[0]);

            let t = self.state[1] << 17;

            self.state[2] ^= self.state[0];
            self.state[3] ^= self.state[1];
            self.state[1] ^= self.state[2];
            self.state[0] ^= self.state[3];

            self.state[2] ^= t;
            self.state[3] = self.state[3].rotate_left(45);

            result
        }

        pub fn gen_range(&mut self, range: std::ops::Range<usize>) -> usize {
            let range_size = range.end - range.start;
            if range_size == 0 {
                return range.start;
            }

            let rand_val = self.next() as usize;
            range.start + (rand_val % range_size)
        }

        pub fn random<T>(&mut self) -> T
        where
            T: FromRandom,
        {
            T::from_random(self)
        }
    }

    pub trait FromRandom {
        fn from_random(rng: &mut Xoshiro256PlusPlus) -> Self;
    }

    impl FromRandom for f64 {
        fn from_random(rng: &mut Xoshiro256PlusPlus) -> Self {
            let val = rng.next();
            (val >> 11) as f64 * (1.0 / (1u64 << 53) as f64)
        }
    }

    impl FromRandom for bool {
        fn from_random(rng: &mut Xoshiro256PlusPlus) -> Self {
            rng.next() & 1 == 1
        }
    }

    pub fn thread_rng() -> Xoshiro256PlusPlus {
        Xoshiro256PlusPlus::from_entropy()
    }
}

#[allow(dead_code)]
mod util {
    //! よく使われるユーティリティ関数をまとめたモジュール

    use std::{
        fmt::Display,
        io::{self, BufWriter, Write as _},
    };

    use num::PrimInt;

    /// 最小値と最大値を更新するトレイト
    ///
    /// # Examples
    ///
    /// ```
    /// use cp_lib_rs::util::ChangeMinMax;
    ///
    /// let mut x = 10;
    /// assert!(x.change_min(3));
    /// assert_eq!(x, 3);
    /// ```
    pub trait ChangeMinMax {
        fn change_min(&mut self, v: Self) -> bool;
        fn change_max(&mut self, v: Self) -> bool;
    }

    impl<T: PartialOrd> ChangeMinMax for T {
        fn change_min(&mut self, v: T) -> bool {
            *self > v && {
                *self = v;
                true
            }
        }

        fn change_max(&mut self, v: T) -> bool {
            *self < v && {
                *self = v;
                true
            }
        }
    }

    /// 条件に従ってYes/Noを出力する
    ///
    /// # Examples
    ///
    /// ```
    /// use cp_lib_rs::yesno;
    ///
    /// let n = 3;
    /// yesno!(3 % 2 == 0)
    /// ```
    #[macro_export]
    macro_rules! yesno {
        ($p:expr) => {
            if $p {
                println!("Yes");
            } else {
                println!("No");
            }
        };
    }

    /// 標準出力・標準エラー出力に出力するトレイト
    ///
    /// # Examples
    ///
    /// ```
    /// use cp_lib_rs::util::PrintLine as _;
    ///
    /// let x = 5;
    /// x.println();
    /// x.eprintln();
    ///
    /// let y = [1, 2, 3];
    /// y.println();
    /// y.eprintln();
    /// ```
    pub trait PrintLine {
        fn println(&self);
        fn eprintln(&self);
    }

    /// 単体値版
    impl<T: Display> PrintLine for T {
        fn println(&self) {
            println!("{self}");
        }

        fn eprintln(&self) {
            eprintln!("{self}");
        }
    }

    /// スライス版
    impl<T: Display> PrintLine for [T] {
        fn println(&self) {
            let stdout = io::stdout();
            let mut out = BufWriter::new(stdout.lock());

            let mut first = true;
            for x in self {
                if !first {
                    out.write_all(b" ").unwrap();
                }
                write!(out, "{x}").unwrap();
                first = false;
            }

            out.write_all(b"\n").unwrap();
            // drop(out)でflush
        }

        fn eprintln(&self) {
            let stderr = io::stderr();
            let mut out = BufWriter::new(stderr.lock());

            let mut first = true;
            for x in self {
                if !first {
                    out.write_all(b" ").unwrap();
                }
                write!(out, "{x}").unwrap();
                first = false;
            }

            out.write_all(b"\n").unwrap();
        }
    }

    /// 多次元配列を作成する
    ///
    /// # Examples
    ///
    /// ```
    /// use cp_lib_rs::mat;
    ///
    /// let a = mat![0; 4; 3];
    /// assert_eq!(a, vec![vec![0; 3]; 4]);
    /// ```
    #[macro_export]
    macro_rules! mat {
	($($e:expr),*) => { vec![$($e),*] };
	($($e:expr,)*) => { vec![$($e),*] };
	($e:expr; $d:expr) => { vec![$e; $d] };
	($e:expr; $d:expr $(; $ds:expr)+) => { vec![mat![$e $(; $ds)*]; $d] };
}

    /// 整数の二分探索を行う
    ///
    /// # Examples
    ///
    /// ```
    /// use cp_lib_rs::util::binary_search;
    ///
    /// let result = binary_search(0, 10, |x| x * x <= 5);
    /// assert_eq!(result, 2);
    /// ```
    pub fn binary_search<T: PrimInt>(ok: T, ng: T, f: impl Fn(T) -> bool) -> T {
        let mut ok = ok;
        let mut ng = ng;

        while ok.max(ng) - ok.min(ng) > T::one() {
            let mid = (ok + ng) / (T::one() << 1);

            if f(mid) {
                ok = mid;
            } else {
                ng = mid;
            }
        }

        ok
    }

    #[cfg(test)]
    mod test {
        use super::*;

        #[test]
        fn binary_search_test() {
            assert_eq!(binary_search(0, 10, |x| x * x <= 5), 2);
            assert_eq!(binary_search(10, 0, |x| x * x >= 5), 3);
        }
    }
}