結果

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

ソースコード

diff #
raw source code 

#![allow(non_snake_case)]
use itertools::Itertools;
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 = vec![];

    for s in 0..k {
        let mut v = vec![];
        for i in (0..).take_while(|&u| s + u * k < n) {
            v.push(p[s + i * k]);
        }

        let m = v.len();
        while !v.is_sorted() {
            for i in 0..m - 1 {
                if v[i] > v[i + 1] {
                    v.swap(i, i + 1);
                    res.push((s + i * k + 1, s + (i + 1) * k + 1));
                }
            }
        }

        for i in 0..m {
            sorted[s + k * i] = v[i];
        }
    }

    if sorted.is_sorted() {
        println!("{}", res.len());
        println!("{}", res.into_iter().map(|(i, j)| format!("{i} {j}")).join("\n"));
    } else {
        println!("-1")
    }
}
0