結果

問題 No.133 カードゲーム
コンテスト
ユーザー RheoTommy
提出日時 2020-11-05 22:28:49
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 1 ms / 5,000 ms
コード長 3,797 bytes
コンパイル時間 17,954 ms
コンパイル使用メモリ 378,044 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-22 11:36:36
合計ジャッジ時間 19,082 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![allow(unused_macros)]
#![allow(dead_code)]
#![allow(unused_imports)]

use crate::lib::{Scanner, Permutation};
use std::collections::*;

const U_INF: usize = 1 << 60;
const I_INF: isize = 1 << 60;

fn main() {
    let mut sc = Scanner::new();
    let n = sc.next_usize();
    let a = (0..n).map(|_| sc.next_usize()).collect::<Vec<_>>();
    let b = (0..n).map(|_| sc.next_usize()).collect::<Vec<_>>();
    let p = Permutation::new(&(0..n).collect());
    let mut win = 0;
    let mut sum = 0;
    for c in p.clone() {
        for d in p.clone() {
            let mut score = 0;
            for i in 0..n {
                if a[c[i]] > b[d[i]] {
                    score += 1;
                } else {
                    score -= 1;
                }
            }
            if score > 0 {
                win += 1;
            }
            sum += 1;
        }
    }
    println!("{}", win as f64 / sum 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;
        }
    }

    pub struct Scanner {
        buf: std::collections::VecDeque<String>,
    }

    impl Scanner {
        pub fn new() -> Self {
            Self {
                buf: std::collections::VecDeque::new(),
            }
        }

        fn scan_line(&mut self) {
            let mut flag = 0;
            while self.buf.is_empty() {
                let mut s = String::new();
                std::io::stdin().read_line(&mut s).unwrap();
                let mut iter = s.split_whitespace().peekable();
                if iter.peek().is_none() {
                    if flag >= 5 {
                        panic!("There is no input!");
                    }
                    flag += 1;
                    continue;
                }

                for si in iter {
                    self.buf.push_back(si.to_string());
                }
            }
        }

        pub fn next<T: std::str::FromStr>(&mut self) -> T {
            self.scan_line();
            self.buf
                .pop_front()
                .unwrap()
                .parse()
                .unwrap_or_else(|_| panic!("Couldn't parse!"))
        }

        pub fn next_usize(&mut self) -> usize {
            self.next()
        }

        pub fn next_isize(&mut self) -> isize {
            self.next()
        }

        pub fn next_chars(&mut self) -> Vec<char> {
            self.next::<String>().chars().collect()
        }

        pub fn next_string(&mut self) -> String {
            self.next()
        }

        pub fn next_char(&mut self) -> char {
            self.next()
        }

        pub fn next_float(&mut self) -> f64 {
            self.next()
        }
    }
}
0