結果

問題 No.241 出席番号(1)
ユーザー hatoo
提出日時 2017-11-12 20:44:41
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 4,280 bytes
コンパイル時間 11,498 ms
コンパイル使用メモリ 378,824 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-30 21:42:24
合計ジャッジ時間 12,828 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
#[allow(unused_imports)]
use std::collections::{HashMap, HashSet, BinaryHeap};
#[allow(unused_imports)]
use std::iter::FromIterator;
#[allow(unused_imports)]
use std::io::stdin;
mod util {
    use std::io::stdin;
    use std::str::FromStr;
    use std::fmt::Debug;
    #[allow(dead_code)]
    pub fn line() -> String {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        line.trim().to_string()
    }
    #[allow(dead_code)]
    pub fn gets<T: FromStr>() -> Vec<T>
    where
        <T as FromStr>::Err: Debug,
    {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        line.split_whitespace()
            .map(|t| t.parse().unwrap())
            .collect()
    }
}
#[allow(unused_macros)]
macro_rules! get {
    ($t:ty) => {
        {
            let mut line: String = String::new();
            stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t:ty),*) => {
        {
            let mut line: String = String::new();
            stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            (
                $(iter.next().unwrap().parse::<$t>().unwrap(),)*
            )
        }
    };
    ($t:ty; $n:expr) => {
        (0..$n).map(|_|
                    get!($t)
                   ).collect::<Vec<_>>()
    };
    ($($t:ty),*; $n:expr) => {
        (0..$n).map(|_|
                    get!($($t),*)
                   ).collect::<Vec<_>>()
    };
    ($t:ty ;;) => {
        {
            let mut line: String = String::new();
            stdin().read_line(&mut line).unwrap();
            line.split_whitespace()
                .map(|t| t.parse::<$t>().unwrap())
                .collect::<Vec<_>>()
        }
    };
}
#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        println!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}
struct Flow {
    // to, capacity, rev
    edges: Vec<Vec<(usize, usize, usize)>>,
}
impl Flow {
    fn new(max_size: usize) -> Flow {
        Flow { edges: vec![Vec::new(); max_size] }
    }
    fn add_edge(&mut self, from: usize, to: usize, cap: usize) {
        let from_rev = self.edges[to].len();
        let to_rev = self.edges[from].len();
        self.edges[from].push((to, cap, from_rev));
        self.edges[to].push((from, 0, to_rev));
    }
    fn max_flow(&mut self, s: usize, t: usize) -> usize {
        let mut flow = 0;
        let l = self.edges.len();
        loop {
            let f = self.dfs(s, t, usize::max_value(), &mut vec![false; l]);
            if f == 0 {
                break;
            }
            flow += f;
        }
        flow
    }
    fn dfs(&mut self, v: usize, t: usize, f: usize, used: &mut [bool]) -> usize {
        if v == t {
            return f;
        }
        used[v] = true;
        for i in 0..self.edges[v].len() {
            let (to, cap, rev) = self.edges[v][i];
            if !used[to] && cap > 0 {
                let d = self.dfs(to, t, min(f, cap), used);
                if d > 0 {
                    self.edges[v][i].1 -= d;
                    self.edges[to][rev].1 += d;
                    return d;
                }
            }
        }
        0
    }
}
fn main() {
    let n = get!(usize);
    let a = get!(usize; n);
    let mut flow = Flow::new(4 * n + 1);
    let s = 0;
    let t = 3 * n + 1;
    for i in 0..n {
        flow.add_edge(0, i + 1, 1);
        flow.add_edge(n + 1 + 2 * i, n + 1 + 2 * i + 1, 1);
        flow.add_edge(n + 1 + 2 * i + 1, t, 1);
        for k in 0..n {
            if k == a[i] {
                continue;
            }
            flow.add_edge(i + 1, n + 1 + 2 * k, 1);
        }
    }
    if flow.max_flow(s, t) == n {
        for i in 0..n {
            for k in 0..flow.edges[i + 1].len() {
                let to = flow.edges[i + 1][k].0;
                let rev = flow.edges[i + 1][k].2;
                if flow.edges[to][rev].1 > 0 {
                    println!("{}", (to - 1 - n) / 2);
                    break;
                }
            }
        }
    } else {
        println!("-1");
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0