結果

問題 No.3775 Distant Swap
コンテスト
ユーザー reicalgrst
提出日時 2026-10-29 14:16:42
言語 Rust
(1.99.1 + proconio + num + itertools + ACL)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
WA  
実行時間 -
コード長 1,269 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,985 ms
コンパイル使用メモリ 178,736 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2026-10-29 14:17:26
合計ジャッジ時間 6,050 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge5_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 2
other AC * 11 WA * 9
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#![allow(non_snake_case)]
use ac_library::segtree::{Additive, Segtree};
use proconio::*;

// https://maguro.dev/blog/debug-macro/
#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),* $(,)*) => {
        #[cfg(debug_assertions)]
        eprintln!(concat!($("| ", stringify!($a), " = {:?} "),*, "|"), $(&$a),*);
    };
}

fn main() {
    std::thread::Builder::new()
        .stack_size(256 * 1024 * 1024)
        .spawn(solve)
        .unwrap()
        .join()
        .unwrap();
}

// K 個飛ばしで sort する
// swap 回数は転倒数
// sort して 全体が sort されてれば OK

fn solve() {
    input! {
        n: usize, k: usize,
        p: [usize; n]
    }

    let mut sorted = vec![0; n];
    let mut res = 0;

    for s in 0..k {
        let mut v = vec![];
        let mut st = Segtree::<Additive<usize>>::from_iter(std::iter::repeat(0).take(n + 1));

        for i in (0..).take_while(|&u| s + u * k < n) {
            let x = p[s + i * k];
            res += st.prod(0..=x);
            st.set(x, 1);
            v.push(x);
        }

        v.sort();
        for i in 0..v.len() {
            sorted[s + k * i] = v[i];
        }
    }

    if sorted.is_sorted() {
        println!("{res}");
    } else {
        println!("-1")
    }
}
0