結果

問題 No.382 シャイな人たち (2)
ユーザー akakimidoriakakimidori
提出日時 2021-10-02 12:13:04
言語 Rust
(1.77.0 + proconio)
結果
TLE  
実行時間 -
コード長 2,783 bytes
コンパイル時間 15,843 ms
コンパイル使用メモリ 405,632 KB
実行使用メモリ 15,808 KB
最終ジャッジ日時 2024-07-20 05:48:27
合計ジャッジ時間 34,960 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
権限があれば一括ダウンロードができます

ソースコード

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 min = (self.size as u32, 0);
        for x in BitOne(rem) {
            let c = (self.edge[x] & rem).count_ones();
            min = (c, x).min(min);
        }
        let (deg, v) = min;
        if deg <= 2 {
            let (x, y) = self.rec(rem & !self.edge[v]);
            (x + 1, y | (1 << v))
        } else {
            let mut ans = (0, 0);
            for v in BitOne(rem & self.edge[v]) {
                let (x, y) = self.rec(rem & !self.edge[v]);
                ans = ans.max((x + 1, y | (1 << v)));
            }
            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
        };
        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