結果

問題 No.3441 Sort Permutation 2
コンテスト
ユーザー elphe
提出日時 2026-02-06 22:55:31
言語 Rust
(1.92.0 + proconio + num + itertools)
結果
WA  
実行時間 -
コード長 1,743 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,071 ms
コンパイル使用メモリ 211,324 KB
実行使用メモリ 30,056 KB
最終ジャッジ日時 2026-02-06 22:55:55
合計ジャッジ時間 16,799 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14 WA * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

fn main() {
    let stdin = std::io::read_to_string(std::io::stdin()).unwrap();
    let mut stdin = stdin.split_ascii_whitespace();

    let n: usize = stdin.next().unwrap().parse().unwrap();
    let p: Vec<u32> = (0..n)
        .map(|_| stdin.next().unwrap().parse().unwrap())
        .collect();

    println!("{}", output(solve(p)));
}

fn prepare(max_n: usize) -> Vec<Vec<u32>> {
    let mut divisors_of = vec![Vec::new(); max_n + 1];
    for i in 1..=max_n {
        for j in (1..).take_while(|&j| i * j <= max_n) {
            divisors_of[i * j].push(i as u32);
        }
    }
    divisors_of
}

fn solve(p: Vec<u32>) -> Vec<u32> {
    let divisors_of = prepare(200_000);
    let mut is_visited = vec![false; p.len()];
    let mut ans = vec![0; p.len()];
    for i in 0..p.len() {
        if !is_visited[i] {
            let mut count_of = std::collections::HashMap::new();
            let mut cur = i;
            while !is_visited[cur] {
                is_visited[cur] = true;
                for &j in &divisors_of[cur.abs_diff((p[cur] - 1) as usize)] {
                    match count_of.get_mut(&j) {
                        Some(target) => {
                            *target += 1;
                        }
                        None => {
                            count_of.insert(j, 1_u32);
                        }
                    }
                }
                cur = (p[cur] - 1) as usize;
            }
            for (value, count) in count_of.into_iter() {
                ans[value as usize] += count - 1;
            }
        }
    }
    ans
}

fn output(ans: Vec<u32>) -> String {
    ans.into_iter()
        .skip(1)
        .map(|x| x.to_string())
        .collect::<Vec<_>>()
        .join("\n")
}
0