結果

問題 No.1053 ゲーミング棒
コンテスト
ユーザー Yukino DX.
提出日時 2024-08-22 14:51:24
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 28 ms / 2,000 ms
コード長 3,022 bytes
コンパイル時間 18,235 ms
コンパイル使用メモリ 401,672 KB
実行使用メモリ 10,368 KB
最終ジャッジ日時 2024-08-22 14:51:45
合計ジャッジ時間 15,194 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

use proconio::input;

fn main() {
    input! {
        n:usize,
        a:[usize;n],
    }

    let mut seen = vec![false; n + 1];
    let mut prev = 0;
    let mut ok = true;
    for i in 0..n {
        if prev != a[i] && seen[a[i]] {
            ok = false;
            break;
        }

        seen[a[i]] = true;
        prev = a[i];
    }
    if ok {
        println!("0");
        return;
    }

    let mut poss = vec![vec![]; n + 1];
    for i in 0..n {
        poss[a[i]].push(i as i64);
    }

    let mut ok = true;
    for i in 0..=n {
        if poss[i].len() <= 1 {
            continue;
        }

        let mut uf = UnionFindTree::new(poss[i].len());
        f(n, poss[i].len(), &poss[i], &mut uf);
        if uf.nofcc() != 1 {
            ok = false;
        }
    }

    let ans = if ok { 1 } else { -1 };

    println!("{}", ans);
}

fn f(m: usize, n: usize, a: &Vec<i64>, uf: &mut UnionFindTree) {
    for i in 0..n {
        let l = (a[i] - a[(i as i64 - 1).rem_euclid(n as i64) as usize]).rem_euclid(m as i64);
        if l == 1 {
            uf.unite(i, (i as i64 - 1).rem_euclid(n as i64) as usize);
        }
        let r = (a[(i + 1) % n] - a[i]).rem_euclid(m as i64);
        if r == 1 {
            uf.unite(i, (i + 1) % n);
        }
    }
}

use unionfindtree::*;
mod unionfindtree {
    pub struct UnionFindTree {
        par: Vec<usize>,
        rank: Vec<usize>,
        size: Vec<usize>,
    }

    impl UnionFindTree {
        pub fn new(n: usize) -> Self {
            Self {
                par: (0..n).collect::<Vec<_>>(),
                rank: vec![0; n],
                size: vec![1; n],
            }
        }

        #[allow(dead_code)]
        pub fn same(&mut self, v1: usize, v2: usize) -> bool {
            self.root(v1) == self.root(v2)
        }

        #[allow(dead_code)]
        pub fn size(&mut self, v: usize) -> usize {
            let v_root = self.root(v);
            self.size[v_root]
        }

        #[allow(dead_code)]
        pub fn root(&mut self, v: usize) -> usize {
            if self.par[v] != v {
                self.par[v] = self.root(self.par[v]);
            }

            self.par[v]
        }

        pub fn unite(&mut self, v1: usize, v2: usize) {
            let mut v1_root = self.root(v1);
            let mut v2_root = self.root(v2);
            if v1_root == v2_root {
                return;
            }

            if self.rank[v1_root] < self.rank[v2_root] {
                std::mem::swap(&mut v1_root, &mut v2_root);
            }

            self.par[v2_root] = v1_root;
            self.size[v1_root] += self.size[v2_root];

            if self.rank[v1_root] == self.rank[v2_root] {
                self.rank[v1_root] += 1;
            }
        }

        #[allow(dead_code)]
        pub fn nofcc(&mut self) -> usize {
            let n = self.par.len();
            (0..n)
                .map(|v| self.root(v))
                .collect::<std::collections::HashSet<usize>>()
                .len()
        }
    }
}
0