#1189008 (Rust) No.3726 Flawless Flow

• 問題: No.3726 Flawless Flow
• ユーザー: 👑 terry_u16
• 提出日時: 2026-09-19 16:18:14
• 言語: Rust (1.97.1 + proconio + num + itertools + ACL)
• 結果: WA
• 実行時間: -
• コード長: 9,416 bytes
• コンパイル時間: 3,462 ms
• コンパイル使用メモリ: 210,628 KB
• 実行使用メモリ: 10,052 KB
• 最終ジャッジ日時: 2026-09-19 16:20:31
• 合計ジャッジ時間: 124,610 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge5_0

ファイルパターン	結果
sample	AC * 1
other	AC * 43 WA * 16

コンパイルメッセージ

warning: unused import: `Duration`
 --> src/main.rs:1:17
  |
1 | use std::time::{Duration, Instant};
  |                 ^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` (part of `#[warn(unused)]`) on by default

ソースコード

use std::time::{Duration, Instant};

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

use crate::rand::Xoshiro256PlusPlus;

fn main() {
    input! {
        n: usize,
        a: [Usize1; n],
        b: [Usize1; n],
    }

    let mut p = vec![0; n];
    let mut inv_b = vec![0; n];

    for i in 0..n {
        inv_b[b[i]] = i;
    }

    for i in 0..n {
        p[i] = inv_b[a[i]];
    }

    eprintln!("{:?}", p);

    let each_duration = 1.95 / n as f64;

    let mut results = vec![p.clone()];

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

    for _ in 0..n {
        let since = Instant::now();

        let mut q = p.clone();
        let mut score = 0;

        for i in 0..n {
            let diff = q[i].abs_diff(i);
            score += diff * diff;
        }

        let mut iter = 0;
        let temp0 = 3e3f64;
        let temp1 = 3e-1f64;
        let mut temp = temp0;

        loop {
            iter += 1;

            if iter % 128 == 0 {
                let time = since.elapsed().as_secs_f64() / each_duration;

                if time >= 1.0 {
                    break;
                }

                temp = temp0.powf(1.0 - time) * temp1.powf(time);
            }

            let index = rng.gen_range(0..n - 1);

            let d1 = index.abs_diff(q[index]);
            let d2 = (index + 1).abs_diff(q[index + 1]);

            let mut new_score = score - d1 * d1 - d2 * d2;

            q.swap(index, index + 1);

            let ok1 = p.get(index - 1) == Some(&q[index])
                || p.get(index) == Some(&q[index])
                || p.get(index + 1) == Some(&q[index]);
            let ok2 = p.get(index) == Some(&q[index + 1])
                || p.get(index + 1) == Some(&q[index + 1])
                || p.get(index + 2) == Some(&q[index + 1]);

            if !ok1 || !ok2 {
                q.swap(index, index + 1);
                continue;
            }

            let d1 = index.abs_diff(q[index]);
            let d2 = (index + 1).abs_diff(q[index + 1]);
            new_score += d1 * d1 + d2 * d2;

            let score_diff = new_score as f64 - score as f64;

            if score_diff <= 0.0
                || (-score_diff / temp).exp() > rng.gen_range(0..1000000) as f64 / 1000000.0
            {
                score = new_score;
            } else {
                q.swap(index, index + 1);
            }
        }

        eprintln!("iter: {}", iter);
        results.push(q.clone());
        p = q;
    }

    if p == (0..n).collect_vec() {
        for p in results.iter() {
            println!("{}", p.iter().map(|&pi| b[pi] + 1).join(" "));
        }
    } else {
        println!("-1");
    }
}

#[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);
        }
    }
}