結果

問題 No.1267 Stop and Coin Game
コンテスト
ユーザー Strorkis
提出日時 2020-10-24 13:11:04
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 70 ms / 2,000 ms
コード長 3,662 bytes
コンパイル時間 13,840 ms
コンパイル使用メモリ 378,820 KB
実行使用メモリ 9,016 KB
最終ジャッジ日時 2024-07-21 15:12:43
合計ジャッジ時間 13,921 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 43
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use std::io::{self, BufRead, Write};
use std::str::FromStr;
use std::fmt;

struct Io1<T>(T);

impl<T: FromStr> FromStr for Io1<T> {
    type Err = String;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        Ok(s.trim_end().parse().ok().unwrap())
    }
}

struct Io2<T1, T2>(T1, T2);

impl<T1: FromStr, T2: FromStr> FromStr for Io2<T1, T2> {
    type Err = String;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        let mut iter = s.split_whitespace();
        Ok(Io2(
            iter.next().unwrap().parse().ok().unwrap(),
            iter.next().unwrap().parse().ok().unwrap(),
        ))
    }
}

struct Io3<T1, T2, T3>(T1, T2, T3);

impl<T1, T2, T3> FromStr for Io3<T1, T2, T3>
where
    T1: FromStr, T2: FromStr, T3: FromStr
{
    type Err = String;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        let mut iter = s.split_whitespace();
        Ok(Io3(
            iter.next().unwrap().parse().ok().unwrap(),
            iter.next().unwrap().parse().ok().unwrap(),
            iter.next().unwrap().parse().ok().unwrap(),
        ))
    }
}

struct Ios(Vec<char>);

impl std::str::FromStr for Ios {
    type Err = String;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        Ok(Ios(s.chars().collect()))
    }
}

impl fmt::Display for Ios {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{}", self.0.iter().collect::<String>())
    }
}

struct Iov<T>(Vec<T>);

impl<T: FromStr> FromStr for Iov<T> {
    type Err = String;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        let iter = s.split_whitespace();
        Ok(Iov(iter.map(|x| x.parse().ok().unwrap()).collect()))
    }
}

impl<T: fmt::Display> fmt::Display for Iov<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{}",
            self.0.iter().map(|x| x.to_string())
                .collect::<Vec<_>>().join(" ")
        )
    }
}

use std::collections::HashMap;

struct Solver<'a> {
    reader: io::BufReader<io::StdinLock<'a>>,
    writer: io::BufWriter<io::StdoutLock<'a>>,
}

impl Solver<'_> {
    fn read<T: FromStr>(&mut self) -> T {
        let mut input = String::new();
        self.reader.read_line(&mut input).unwrap();
        input.trim_end().parse().ok().unwrap()
    }

    fn writeln<T: fmt::Display>(&mut self, ans: T) {
        writeln!(self.writer, "{}", ans).unwrap();
    }

    fn rec(
        n: usize, a: &Vec<i64>, map: &mut HashMap<i32, bool>,
        v: i64, mut state: i32, flag: bool
    ) -> bool {
        if v < 0 { return flag; }
        if let Some(value) = map.get(&state) { return *value; }

        for i in 0..n {
            if state & 1 << i != 0 { continue; }
            state |= 1 << i;
            let value = Self::rec(n, a, map, v - a[i], state, !flag);
            map.insert(state, value);
            if value == flag { return flag; }
            state ^= 1 << i;
        }
        !flag
    }

    fn solve(&mut self) {
        let Io2(n, v): Io2<usize, i64> = self.read();
        let Iov(a): Iov<i64> = self.read();

        if a.iter().sum::<i64>() <= v {
            return self.writeln("Draw");
        }
        
        let mut map = HashMap::new();
        if Self::rec(n, &a, &mut map, v, 0, true) {
            self.writeln("First");
        } else {
            self.writeln("Second");
        }
    }

    fn run() {
        let (stdin, stdout) = (io::stdin(), io::stdout());
        let reader = io::BufReader::new(stdin.lock());
        let writer = io::BufWriter::new(stdout.lock());
        let mut solver = Solver { reader, writer };
        solver.solve();
    }
}

fn main() {
    Solver::run();
}
0