結果

問題 No.3262 水色コーダーさん、その問題d問題ですよ？（1<=d<=N）
コンテスト
ユーザー EvbCFfp1XB
提出日時 2025-10-15 21:52:32
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 4 ms / 2,000 ms
コード長 872 bytes
コンパイル時間 13,182 ms
コンパイル使用メモリ 398,320 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-10-15 21:52:47
合計ジャッジ時間 13,217 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

use proconio::input;

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

    println!("{}", dfs(0, n, &mut vec![false; n], &mut vec![0; n], &lr));
}

fn dfs(i: usize, n: usize, used: &mut [bool], permutation: &mut [usize], lr: &[(i64, i64)]) -> i64 {
    if i >= n {
        return if is_valid(permutation, lr) { 1 } else { 0 };
    }
    let mut res = 0;
    for v in 0..n {
        if used[v] {
            continue;
        }
        used[v] = true;
        permutation[i] = v;
        res += dfs(i + 1, n, used, permutation, lr);
        used[v] = false;
    }
    res
}

fn is_valid(permutation: &[usize], lr: &[(i64, i64)]) -> bool {
    let mut difficulty = 0;
    for (l, r) in permutation.iter().map(|&i| lr[i]) {
        if difficulty > r {
            return false;
        }
        difficulty = difficulty.max(l);
    }
    true
}
0