結果

問題 No.3262 水色コーダーさん、その問題d問題ですよ？（1<=d<=N）
コンテスト
ユーザー yiwiy9
提出日時 2025-09-09 00:48:22
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,120 bytes
コンパイル時間 13,059 ms
コンパイル使用メモリ 378,980 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2025-09-09 00:48:38
合計ジャッジ時間 14,878 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use proconio::{input, marker::Usize1};

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

    let mut order = (0..n).collect::<Vec<usize>>();
    let mut ans = 0;

    // Heap's algorithmによる順列生成
    heap_recursive(&mut order, n, &lr, &mut ans);

    println!("{}", ans);
}

fn heap_recursive(order: &mut Vec<usize>, k: usize, lr: &[(usize, usize)], ans: &mut i32) {
    if k == 1 {
        // 順列をチェック
        let mut ok = true;
        let mut max_left = lr[order[0]].0;
        for i in 1..order.len() {
            let (l, r) = lr[order[i]];
            if max_left > r {
                ok = false;
                break;
            }
            max_left = max_left.max(l);
        }
        if ok {
            *ans += 1;
        }
        return;
    }

    for i in 0..k {
        heap_recursive(order, k - 1, lr, ans);

        // Heap's algorithm: kが偶数なら最初の要素と交換、奇数ならi番目と交換
        if k % 2 == 0 {
            order.swap(i, k - 1);
        } else {
            order.swap(0, k - 1);
        }
    }
}
0