結果
問題 | No.470 Inverse S+T Problem |
ユーザー |
|
提出日時 | 2017-10-19 17:29:27 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 168 ms / 2,000 ms |
コード長 | 3,875 bytes |
コンパイル時間 | 13,201 ms |
コンパイル使用メモリ | 402,708 KB |
実行使用メモリ | 7,424 KB |
最終ジャッジ日時 | 2024-12-22 13:48:15 |
合計ジャッジ時間 | 14,750 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 27 |
コンパイルメッセージ
warning: unnecessary parentheses around type --> src/main.rs:131:12 | 131 | let n: (usize) = util::get(); | ^ ^ | = note: `#[warn(unused_parens)]` on by default help: remove these parentheses | 131 - let n: (usize) = util::get(); 131 + let n: usize = util::get(); |
ソースコード
#[allow(unused_imports)]use std::cmp::{max, min, Ordering};#[allow(unused_imports)]use std::collections::{HashMap, HashSet};mod util {use std::io::stdin;use std::str::FromStr;use std::fmt::Debug;#[allow(dead_code)]pub fn line() -> String {let mut line: String = String::new();stdin().read_line(&mut line).unwrap();line.trim().to_string()}#[allow(dead_code)]pub fn get<T: FromStr>() -> Twhere<T as FromStr>::Err: Debug,{let mut line: String = String::new();stdin().read_line(&mut line).unwrap();line.trim().parse().unwrap()}#[allow(dead_code)]pub fn gets<T: FromStr>() -> Vec<T>where<T as FromStr>::Err: Debug,{let mut line: String = String::new();stdin().read_line(&mut line).unwrap();line.split_whitespace().map(|t| t.parse().unwrap()).collect()}#[allow(dead_code)]pub fn get2<T: FromStr, U: FromStr>() -> (T, U)where<T as FromStr>::Err: Debug,<U as FromStr>::Err: Debug,{let mut line: String = String::new();stdin().read_line(&mut line).unwrap();let mut iter = line.split_whitespace();(iter.next().unwrap().parse().unwrap(),iter.next().unwrap().parse().unwrap(),)}#[allow(dead_code)]pub fn get3<S: FromStr, T: FromStr, U: FromStr>() -> (S, T, U)where<S as FromStr>::Err: Debug,<T as FromStr>::Err: Debug,<U as FromStr>::Err: Debug,{let mut line: String = String::new();stdin().read_line(&mut line).unwrap();let mut iter = line.split_whitespace();(iter.next().unwrap().parse().unwrap(),iter.next().unwrap().parse().unwrap(),iter.next().unwrap().parse().unwrap(),)}}// std::cmp::Reverse doesn't have Clone.#[derive(Eq, PartialEq, Clone)]struct Rev<T>(pub T);impl<T: PartialOrd> PartialOrd for Rev<T> {fn partial_cmp(&self, other: &Rev<T>) -> Option<Ordering> {other.0.partial_cmp(&self.0)}}impl<T: Ord> Ord for Rev<T> {fn cmp(&self, other: &Rev<T>) -> Ordering {other.0.cmp(&self.0)}}#[allow(unused_macros)]macro_rules! debug {($x: expr) => {println!("{}: {:?}", stringify!($x), $x)}}fn dfs(u: &[Vec<char>],i: usize,ans: &mut Vec<(String, String)>,memo: &mut HashSet<String>,) -> bool {if i == u.len() {return true;}for k in 1..3 {let l: String = u[i][..k].iter().cloned().collect();let r: String = u[i][k..].iter().cloned().collect();if !memo.contains(&l) && !memo.contains(&r) {memo.insert(l.clone());memo.insert(r.clone());ans.push((l.clone(), r.clone()));if dfs(u, i + 1, ans, memo) {return true;} else {ans.pop();memo.remove(&l);memo.remove(&r);}}if u[i][0] == u[i][1] && u[i][1] == u[i][2] {break;}}return false;}fn main() {let n: (usize) = util::get();let u: Vec<Vec<char>> = (0..n).map(|_| util::line().chars().collect()).collect();if (0..26).flat_map(|c| {vec![('a' as u8 + c) as char, ('A' as u8 + c) as char].into_iter()}).any({|c| u.iter().filter(|v| v[0] == c && v[2] == c).count() >= 2}){println!("Impossible");return;}let mut ans = Vec::new();if dfs(&u, 0, &mut ans, &mut HashSet::new()) {for &(ref a, ref b) in &ans {println!("{} {}", a, b);}} else {println!("Impossible");}}