結果

問題 No.382 シャイな人たち (2)
コンテスト
ユーザー akakimidori
提出日時 2021-10-02 12:22:40
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 1,089 ms / 8,000 ms
コード長 2,671 bytes
コンパイル時間 14,904 ms
コンパイル使用メモリ 378,712 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-20 05:59:28
合計ジャッジ時間 32,876 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

type BIT = u128;

pub struct BitOne(BIT);

use std::iter::*;

impl Iterator for BitOne {
    type Item = usize;
    fn next(&mut self) -> Option<Self::Item> {
        if self.0 == 0 {
            None
        } else {
            let y = self.0.trailing_zeros() as usize;
            self.0 ^= 1 << y;
            Some(y)
        }
    }
}

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) -> (u32, BIT) {
        if rem == 0 {
            return (0, 0);
        }
        let mut max = (0, 0);
        for v in BitOne(rem) {
            let c = (self.edge[v] & rem).count_ones();
            if c <= 2 {
                let (x, y) = self.rec(rem & !self.edge[v]);
                return (x + 1, y | (1 << v));
            }
            max = (c, v).max(max);
        }
        let v = max.1;
        let a = self.rec(rem ^ (1 << v));
        let (x, y) = self.rec(rem & !self.edge[v]);
        a.max((x + 1, y | (1 << v)))
    }
    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
        };
        let ans = self.rec(mask).1;
        BitOne(ans).collect::<Vec<_>>()
    }
}

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