結果
問題 | No.382 シャイな人たち (2) |
ユーザー | akakimidori |
提出日時 | 2020-05-13 21:39:38 |
言語 | Rust (1.77.0) |
結果 |
AC
|
実行時間 | 1,691 ms / 8,000 ms |
コード長 | 2,719 bytes |
コンパイル時間 | 883 ms |
コンパイル使用メモリ | 153,116 KB |
実行使用メモリ | 4,352 KB |
最終ジャッジ日時 | 2023-10-12 17:06:14 |
合計ジャッジ時間 | 32,061 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,651 ms
4,352 KB |
testcase_01 | AC | 1,691 ms
4,352 KB |
testcase_02 | AC | 1,366 ms
4,348 KB |
testcase_03 | AC | 1,479 ms
4,352 KB |
testcase_04 | AC | 1,335 ms
4,348 KB |
testcase_05 | AC | 1,527 ms
4,352 KB |
testcase_06 | AC | 1,102 ms
4,348 KB |
testcase_07 | AC | 1,570 ms
4,352 KB |
testcase_08 | AC | 1,175 ms
4,352 KB |
testcase_09 | AC | 1,313 ms
4,348 KB |
testcase_10 | AC | 1,296 ms
4,352 KB |
testcase_11 | AC | 1,115 ms
4,352 KB |
testcase_12 | AC | 1,394 ms
4,352 KB |
testcase_13 | AC | 1,405 ms
4,352 KB |
testcase_14 | AC | 1,610 ms
4,348 KB |
testcase_15 | AC | 1,590 ms
4,348 KB |
testcase_16 | AC | 1,324 ms
4,352 KB |
testcase_17 | AC | 1,247 ms
4,348 KB |
testcase_18 | AC | 1,526 ms
4,348 KB |
testcase_19 | AC | 1,316 ms
4,348 KB |
testcase_20 | AC | 1 ms
4,352 KB |
ソースコード
// 以下の提出を多大に参考にしている // 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(); }