結果

問題 No.382 シャイな人たち (2)
コンテスト
ユーザー akakimidori
提出日時 2020-05-13 21:39:38
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 1,725 ms / 8,000 ms
コード長 2,719 bytes
コンパイル時間 21,577 ms
コンパイル使用メモリ 388,416 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-14 15:41:41
合計ジャッジ時間 44,925 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

// 以下の提出を多大に参考にしている
// https://yukicoder.me/submissions/471192

type BIT = u128;

struct Graph {
    size: usize,
    edge: Vec<BIT>,
}

impl Graph {
    fn new(size: usize) -> Self {
        assert!(std::mem::size_of::<BIT>() * 8 >= size);
        Graph {
            size: size,
            edge: (0..size).map(|x| (1 as BIT) << x as BIT).collect(),
        }
    }
    fn add_edge(&mut self, s: usize, t: usize) {
        assert!(s != t);
        self.edge[s] |= (1 as BIT) << t as BIT;
        self.edge[t] |= (1 as BIT) << s as BIT;
    }
    fn rec(&self, rem: BIT) -> Vec<usize> {
        if rem == 0 {
            return vec![];
        }
        let mut max_deg = (0, 0);
        let mut bit = rem;
        while bit > 0 {
            let x = bit & (!bit + 1);
            bit -= x;
            let x = x.trailing_zeros() as usize;
            let deg = (self.edge[x] & rem).count_ones();
            if deg <= 2 {
                let mut ans = self.rec(rem & !self.edge[x]);
                ans.push(x);
                return ans;
            }
            max_deg = std::cmp::max(max_deg, (deg, x));
        }
        let v = max_deg.1;
        let mut ans = self.rec(rem & !self.edge[v]);
        ans.push(v);
        if max_deg.0 <= 3 {
            return ans;
        }
        let q = self.rec(rem & !((1 as BIT) << v as BIT));
        if q.len() > ans.len() {
            q
        } else {
            ans
        }
    }
    fn solve(&self) -> Vec<usize> {
        let mask = if self.size == std::mem::size_of::<BIT>() * 8 {
            !0
        } else {
            ((1 as BIT) << self.size as BIT) - 1
        };
        self.rec(mask)
    }
}

struct RNG {
    s: usize
}

impl RNG {
    fn new(seed: usize) -> Self {
        RNG {
            s: seed,
        }
    }
    fn next(&mut self) -> usize {
        self.s = self.s * 12345 % 1000003;
        self.s
    }
}

fn run() {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    let mut rng = RNG::new(s.trim().parse().unwrap());
    let n: usize = rng.next() % 120 + 2;
    let mut graph = Graph::new(n);
    let p = rng.next();
    let mut cnt = 0;
    for i in 1..=n {
        for j in (i + 1)..=n {
            let e = rng.next();
            if e >= p {
                cnt += 1;
                graph.add_edge(i - 1, j - 1);
            }
        }
    }
    if cnt == 0 {
        println!("-1");
        return;
    }
    let ans = graph.solve();
    let mut out = String::new();
    out.push_str(&format!("{}\n", ans.len() + 1));
    for a in ans {
        out.push_str(&format!("{} ", a + 1));
    }
    out.pop();
    println!("{}", out);
}

fn main() {
    run();
}
0