結果

問題 No.133 カードゲーム
ユーザー kinodjnzkinodjnz
提出日時 2024-05-16 08:59:55
言語 Rust
(1.77.0)
結果
AC  
実行時間 1 ms / 5,000 ms
コード長 1,615 bytes
コンパイル時間 11,368 ms
コンパイル使用メモリ 401,228 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-05-16 09:00:22
合計ジャッジ時間 13,133 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 1 ms
6,812 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 AC 1 ms
6,940 KB
testcase_05 AC 1 ms
6,940 KB
testcase_06 AC 1 ms
6,940 KB
testcase_07 AC 1 ms
6,940 KB
testcase_08 AC 1 ms
6,940 KB
testcase_09 AC 1 ms
6,944 KB
testcase_10 AC 1 ms
6,940 KB
testcase_11 AC 1 ms
6,940 KB
testcase_12 AC 1 ms
6,940 KB
testcase_13 AC 1 ms
6,940 KB
testcase_14 AC 1 ms
6,944 KB
testcase_15 AC 1 ms
6,940 KB
testcase_16 AC 1 ms
6,944 KB
testcase_17 AC 1 ms
6,940 KB
testcase_18 AC 1 ms
6,940 KB
testcase_19 AC 1 ms
6,944 KB
testcase_20 AC 1 ms
6,940 KB
testcase_21 AC 1 ms
6,944 KB
testcase_22 AC 1 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::cmp::Ordering;
use std::io::Read;

fn factorial(x: usize) -> usize {
    if x == 0 {
        1
    } else {
        x * factorial(x - 1)
    }
}

fn permutations(v: &[i64]) -> Vec<Vec<i64>> {
    fn rec(v: &mut [i64], i: usize) -> Vec<Vec<i64>> {
        if v.len() <= i {
            return vec![v.to_vec()];
        }
        let mut res = rec(v, i + 1);
        for j in i + 1..v.len() {
            v.swap(i, j);
            res.append(&mut rec(v, i + 1));
            v.swap(i, j);
        }
        res
    }

    rec(&mut v.to_vec(), 0)
}

fn solve(n: usize, a: &[i64], b: &[i64]) -> f64 {
    let mut a_wins = 0;
    for pa in permutations(a) {
        for pb in permutations(b) {
            let m = pa
                .iter()
                .zip(pb.iter())
                .map(|(x, y)| match x.cmp(y) {
                    Ordering::Greater => 1,
                    Ordering::Less => -1,
                    Ordering::Equal => 0,
                })
                .sum::<i64>();
            if m > 0 {
                a_wins += 1;
            }
        }
    }
    (a_wins as f64) / (factorial(n).pow(2) as f64)
}

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();
    let mut iter = buf.split_whitespace();
    let n: usize = iter.next().unwrap().parse().unwrap();
    let a: Vec<i64> = (0..n)
        .map(|_| iter.next().unwrap().parse().unwrap())
        .collect();
    let b: Vec<i64> = (0..n)
        .map(|_| iter.next().unwrap().parse().unwrap())
        .collect();
    let result = solve(n, &a, &b);
    println!("{}", result);
}
0