結果

問題 No.133 カードゲーム
ユーザー maedamaeda
提出日時 2024-05-01 14:16:51
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 1 ms / 5,000 ms
コード長 2,278 bytes
コンパイル時間 12,999 ms
コンパイル使用メモリ 403,292 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-05-01 14:17:12
合計ジャッジ時間 14,167 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 1 ms
6,816 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,944 KB
testcase_13 AC 1 ms
6,944 KB
testcase_14 AC 1 ms
6,940 KB
testcase_15 AC 1 ms
6,940 KB
testcase_16 AC 1 ms
6,940 KB
testcase_17 AC 1 ms
6,944 KB
testcase_18 AC 1 ms
6,940 KB
testcase_19 AC 1 ms
6,944 KB
testcase_20 AC 1 ms
6,944 KB
testcase_21 AC 1 ms
6,940 KB
testcase_22 AC 1 ms
6,940 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: constant `DX` is never used
  --> src/main.rs:18:7
   |
18 | const DX: [i64; 4] = [0, 0, 1, -1];
   |       ^^
   |
   = note: `#[warn(dead_code)]` on by default

warning: constant `DY` is never used
  --> src/main.rs:19:7
   |
19 | const DY: [i64; 4] = [1, -1, 0, 0];
   |       ^^

ソースコード

diff #

#![allow(non_snake_case)]
#![allow(unused_imports)]
use crate::lib::Permutation;
use proconio::{
    fastout, input, input_interactive,
    marker::{Chars, Isize1, Usize1},
};
use std::vec;

#[allow(dead_code)]
// const MOD: i64 = 1_000_000_007;
// const MOD : i64 = 1_000_000_009;
const MOD: i64 = 998_244_353;

#[allow(dead_code)]
const INF: i64 = 1_010_000_000_000_000_017;

const DX: [i64; 4] = [0, 0, 1, -1];
const DY: [i64; 4] = [1, -1, 0, 0];

#[allow(non_snake_case)]
fn main() {
    input!(N:usize, A:[usize;N], B:[usize;N]);

    let mut count_match = 0;
    let mut count_win_A = 0;
    let p = Permutation::new(&(0..N).collect());

    for perm_A in p.clone() {
        for perm_B in p.clone() {
            count_match += 1;
            let mut win_A = 0;
            for i in 0..N {
                if A[perm_A[i]] > B[perm_B[i]] {
                    win_A += 1;
                }
            }

            if win_A > N / 2 {
                count_win_A += 1;
            }
        }
    }

    println!("{}", count_win_A as f64 / count_match as f64)
}

pub mod lib {
    #[derive(Clone)]
    pub struct Permutation<T: Clone> {
        v: Vec<T>,
        l: Vec<usize>,
        not_start: bool,
    }

    impl<T: Clone> Permutation<T> {
        pub fn new(v: &Vec<T>) -> Permutation<T> {
            Permutation {
                l: vec![0; v.len()],
                v: v.clone(),
                not_start: true,
            }
        }
    }

    impl<T: Clone> Iterator for Permutation<T> {
        type Item = Vec<T>;
        fn next(&mut self) -> Option<Vec<T>> {
            // non-permutated vector
            if self.not_start {
                self.not_start = false;
                return Some(self.v.clone());
            }
            for n in 0..self.v.len() {
                if self.l[n] < n {
                    if (n + 1) % 2 == 1 {
                        self.v.swap(0, n);
                        self.l[n] += 1;
                    } else {
                        self.v.swap(self.l[n], n);
                        self.l[n] += 1;
                    }
                    return Some(self.v.clone());
                } else {
                    self.l[n] = 0
                }
            }
            return None;
        }
    }
}
0