結果
問題 | No.1711 Divide LCM |
ユーザー |
![]() |
提出日時 | 2021-10-15 22:34:47 |
言語 | Rust (1.83.0 + proconio) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,895 bytes |
コンパイル時間 | 13,443 ms |
コンパイル使用メモリ | 392,308 KB |
実行使用メモリ | 93,312 KB |
最終ジャッジ日時 | 2024-09-17 17:44:52 |
合計ジャッジ時間 | 22,162 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 TLE * 1 |
ソースコード
// ---------- begin next_permutation ----------fn next_permutation<T: Ord>(a: &mut [T]) -> bool {a.windows(2).rposition(|a| a[0] < a[1]).map_or(false, |x| {let y = a.iter().rposition(|b| a[x] < *b).unwrap();a.swap(x, y);a[(x + 1)..].reverse();true})}// ---------- end next_permutation ----------// ---------- begin scannner ----------#[allow(dead_code)]mod scanner {use std::str::FromStr;pub struct Scanner<'a> {it: std::str::SplitWhitespace<'a>,}impl<'a> Scanner<'a> {pub fn new(s: &'a String) -> Scanner<'a> {Scanner {it: s.split_whitespace(),}}pub fn next<T: FromStr>(&mut self) -> T {self.it.next().unwrap().parse::<T>().ok().unwrap()}pub fn next_bytes(&mut self) -> Vec<u8> {self.it.next().unwrap().bytes().collect()}pub fn next_chars(&mut self) -> Vec<char> {self.it.next().unwrap().chars().collect()}pub fn next_vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {(0..len).map(|_| self.next()).collect()}}}// ---------- end scannner ----------use std::io::Write;fn main() {use std::io::Read;let mut s = String::new();std::io::stdin().read_to_string(&mut s).unwrap();let mut sc = scanner::Scanner::new(&s);let out = std::io::stdout();let mut out = std::io::BufWriter::new(out.lock());run(&mut sc, &mut out);}fn run<W: Write>(sc: &mut scanner::Scanner, out: &mut std::io::BufWriter<W>) {let n: usize = sc.next();let mut dp = vec![0; 1000000 + 1];let mut a = vec![];for _ in 0..n {let m: usize = sc.next();let mut p = vec![(0usize, 0usize); m];for p in p.iter_mut() {p.0 = sc.next();p.1 = sc.next();dp[p.0] = dp[p.0].max(p.1);}a.push(p);}let mut cond = vec![];for i in 0..dp.len() {if dp[i] > 0 {cond.push(i);}}for a in a.iter() {if a.len() == cond.len() && a.iter().all(|p| p.1 == dp[p.0]) {writeln!(out, "-1").ok();return;}}let mut ban = std::collections::BTreeSet::new();for a in a.iter() {let mut p = vec![];for a in a.iter() {if dp[a.0] == a.1 {p.push(a.0);}}for i in 1..(1 << p.len()) {let mut x = vec![];for (j, p) in p.iter().enumerate() {if i >> j & 1 == 1 {x.push(*p);}}ban.insert(x);}}for k in 2.. {let mut test = vec![0; cond.len()];for t in test.iter_mut().rev().take(k) {*t = 1;}while {let mut x = vec![];for (i, t) in test.iter().enumerate() {if *t > 0 {x.push(cond[i]);}}if !ban.contains(&x) {let mut ans = vec![vec![]; k];for a in a {for (ans, &x) in ans.iter_mut().zip(&x) {if !a.contains(&(x, dp[x])) {ans.push(a.iter().fold(1, |s, a| s * a.0.pow(a.1 as u32)));break;}}}writeln!(out, "{}", ans.len()).ok();for ans in ans {write!(out, "{}", ans.len()).ok();for a in ans {write!(out, " {}", a).ok();}writeln!(out).ok();}return;}next_permutation(&mut test)} {}}}