#611172 (Rust) No.1370 置換門松列

• 問題: No.1370 置換門松列
• ユーザー: akakimidori
• 提出日時: 2021-01-29 21:57:10
• 言語: Rust (1.77.0)
• 結果: WA
• 実行時間: -
• コード長: 5,862 bytes
• コンパイル時間: 1,588 ms
• コンパイル使用メモリ: 178,968 KB
• 実行使用メモリ: 9,968 KB
• 最終ジャッジ日時: 2024-04-25 17:04:23
• 合計ジャッジ時間: 3,300 ms
• ジャッジサーバーID （参考情報）: judge1 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 6,812 KB
testcase_01	AC	1 ms; 6,944 KB
testcase_02	AC	1 ms; 6,940 KB
testcase_03	AC	1 ms; 6,940 KB
testcase_04	AC	1 ms; 6,944 KB
testcase_05	AC	0 ms; 6,940 KB
testcase_06	AC	1 ms; 6,944 KB
testcase_07	AC	1 ms; 6,940 KB
testcase_08	WA	-
testcase_09	AC	1 ms; 6,940 KB
testcase_10	WA	-
testcase_11	AC	1 ms; 6,944 KB
testcase_12	AC	1 ms; 6,940 KB
testcase_13	AC	1 ms; 6,940 KB
testcase_14	AC	0 ms; 6,940 KB
testcase_15	WA	-
testcase_16	AC	1 ms; 6,940 KB
testcase_17	AC	0 ms; 6,940 KB
testcase_18	AC	1 ms; 6,940 KB
testcase_19	AC	0 ms; 6,944 KB
testcase_20	AC	1 ms; 6,944 KB
testcase_21	AC	18 ms; 8,792 KB
testcase_22	AC	11 ms; 9,968 KB
testcase_23	WA	-
testcase_24	AC	6 ms; 6,940 KB
testcase_25	WA	-
testcase_26	WA	-
testcase_27	AC	11 ms; 8,716 KB
testcase_28	AC	11 ms; 8,584 KB
testcase_29	AC	6 ms; 6,944 KB

ソースコード

// ---------- begin SCC ----------
pub struct SCC {
    size: usize,
    edge: Vec<(u32, u32)>,
}

impl SCC {
    pub fn new(size: usize) -> Self {
        assert!(size <= 10usize.pow(8));
        SCC { size, edge: vec![] }
    }
    pub fn add_edge(&mut self, a: usize, b: usize) {
        assert!(a < self.size && b < self.size);
        self.edge.push((a as u32, b as u32));
    }
    pub fn build(&self) -> (usize, Vec<usize>) {
        let size = self.size;
        let mut start = vec![0u32; size + 1];
        self.edge.iter().for_each(|e| start[e.0 as usize + 1] += 1);
        for i in 1..=size {
            start[i] += start[i - 1];
        }
        let mut buf = vec![0; self.edge.len()];
        for &(a, b) in self.edge.iter() {
            let po = &mut start[a as usize];
            buf[*po as usize] = b;
            *po += 1;
        }
        let mut s = 0usize;
        let mut neighbor = start
            .into_iter()
            .take(size)
            .map(|t| {
                let t = t as usize;
                let it = buf[s..t].iter().map(|p| *p as usize);
                s = t;
                it
            })
            .collect::<Vec<_>>();
        let mut ord = vec![size; size];
        let mut assigned = vec![false; size];
        let mut stack_s = vec![];
        let mut stack_p = vec![];
        let mut call = vec![];
        let mut now_ord = 0;
        let mut res = vec![0; size];
        let mut id = 0;
        enum Operation {
            Call(usize),
            Iter(usize),
            Eval(usize),
        }
        for i in 0..size {
            if ord[i] != size {
                continue;
            }
            call.push(Operation::Call(i));
            while let Some(op) = call.pop() {
                match op {
                    Operation::Call(v) => {
                        ord[v] = now_ord;
                        now_ord += 1;
                        stack_s.push(v);
                        stack_p.push(v);
                        call.push(Operation::Eval(v));
                        call.push(Operation::Iter(v));
                    }
                    Operation::Iter(v) => {
                        let it = &mut neighbor[v];
                        while let Some(u) = it.next() {
                            if ord[u] == size {
                                call.push(Operation::Iter(v));
                                call.push(Operation::Call(u));
                                break;
                            } else if !assigned[u] {
                                while ord[*stack_p.last().unwrap()] > ord[u] {
                                    stack_p.pop();
                                }
                            }
                        }
                    }
                    Operation::Eval(v) => {
                        if *stack_p.last().unwrap() == v {
                            while let Some(u) = stack_s.pop() {
                                res[u] = id;
                                assigned[u] = true;
                                if u == v {
                                    break;
                                }
                            }
                            stack_p.pop();
                            id += 1;
                        }
                    }
                }
            }
        }
        res.iter_mut().for_each(|v| *v = id - 1 - *v);
        (id, res)
    }
}
// ---------- end SCC ----------
// ---------- begin input macro ----------
// reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, bytes) => {
        read_value!($iter, String).bytes().collect::<Vec<u8>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
// ---------- end input macro ----------

fn run() {
    input! {
        n: usize,
        m: usize,
        a: [usize1; n],
    }
    if a.windows(2).any(|a| a[0] == a[1]) {
        println!("No");
        return;
    }
    let mut scc = SCC::new(m);
    for (i, a) in a.windows(3).enumerate() {
        if a[0] == a[2] {
            println!("No");
            return;
        }
        if i & 1 == 0 {
            scc.add_edge(a[1], a[0]);
            scc.add_edge(a[1], a[2]);
        } else {
            scc.add_edge(a[0], a[1]);
            scc.add_edge(a[2], a[1]);
        }
    }
    let (len, id) = scc.build();
    if len < m {
        println!("No");
    } else {
        println!("Yes");
        let mut p = vec![0; m];
        for (i, id) in id.iter().enumerate() {
            p[*id] = i + 1;
        }
        let mut s = String::new();
        for a in p {
            s.push_str(&format!("{} ", a + 1));
        }
        s.pop();
        println!("{}", s);
    }
}

fn main() {
    run();
}