結果
問題 | No.1017 Reiwa Sequence |
ユーザー | fukafukatani |
提出日時 | 2020-04-03 23:13:37 |
言語 | Rust (1.72.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,917 bytes |
コンパイル時間 | 1,412 ms |
コンパイル使用メモリ | 161,828 KB |
実行使用メモリ | 298,728 KB |
最終ジャッジ日時 | 2023-09-16 04:36:35 |
合計ジャッジ時間 | 43,620 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 5 ms
5,328 KB |
testcase_01 | AC | 4 ms
5,264 KB |
testcase_02 | AC | 3 ms
5,308 KB |
testcase_03 | AC | 4 ms
6,144 KB |
testcase_04 | AC | 3 ms
5,232 KB |
testcase_05 | AC | 4 ms
5,304 KB |
testcase_06 | AC | 4 ms
5,260 KB |
testcase_07 | AC | 3 ms
5,300 KB |
testcase_08 | AC | 3 ms
5,312 KB |
testcase_09 | AC | 95 ms
41,956 KB |
testcase_10 | AC | 809 ms
150,636 KB |
testcase_11 | AC | 39 ms
23,876 KB |
testcase_12 | AC | 1,011 ms
150,464 KB |
testcase_13 | AC | 763 ms
150,308 KB |
testcase_14 | AC | 38 ms
22,632 KB |
testcase_15 | AC | 90 ms
41,744 KB |
testcase_16 | AC | 41 ms
22,620 KB |
testcase_17 | AC | 524 ms
153,640 KB |
testcase_18 | AC | 41 ms
22,604 KB |
testcase_19 | AC | 1,876 ms
298,728 KB |
testcase_20 | AC | 1,734 ms
294,692 KB |
testcase_21 | AC | 1,717 ms
294,848 KB |
testcase_22 | AC | 1,640 ms
296,312 KB |
testcase_23 | AC | 1,512 ms
294,172 KB |
testcase_24 | AC | 1,337 ms
294,440 KB |
testcase_25 | AC | 1,263 ms
296,952 KB |
testcase_26 | AC | 1,042 ms
294,148 KB |
testcase_27 | WA | - |
testcase_28 | AC | 1,772 ms
294,788 KB |
testcase_29 | AC | 1,780 ms
294,676 KB |
testcase_30 | WA | - |
testcase_31 | AC | 1,387 ms
294,172 KB |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | AC | 3 ms
5,312 KB |
testcase_35 | AC | 3 ms
5,304 KB |
testcase_36 | AC | 3 ms
5,296 KB |
testcase_37 | WA | - |
testcase_38 | WA | - |
testcase_39 | WA | - |
testcase_40 | AC | 24 ms
10,892 KB |
testcase_41 | AC | 24 ms
10,880 KB |
testcase_42 | AC | 23 ms
10,584 KB |
testcase_43 | AC | 24 ms
10,748 KB |
testcase_44 | AC | 24 ms
10,848 KB |
testcase_45 | AC | 23 ms
10,728 KB |
testcase_46 | AC | 23 ms
10,728 KB |
testcase_47 | AC | 22 ms
10,504 KB |
testcase_48 | AC | 38 ms
11,144 KB |
testcase_49 | AC | 35 ms
13,800 KB |
testcase_50 | AC | 25 ms
8,912 KB |
testcase_51 | AC | 4 ms
5,304 KB |
testcase_52 | WA | - |
testcase_53 | WA | - |
ソースコード
#![allow(unused_imports)] #![allow(non_snake_case)] use std::cmp::*; use std::collections::*; use std::io::Write; #[allow(unused_macros)] macro_rules! debug { ($($e:expr),*) => { #[cfg(debug_assertions)] $({ let (e, mut err) = (stringify!($e), std::io::stderr()); writeln!(err, "{} = {:?}", e, $e).unwrap() })* }; } fn yes(a: &Vec<i64>) { println!("Yes"); for &num in a.iter().take(a.len() - 1) { print!("{} ", num); } println!("{}", a[a.len() - 1]); } fn main() { let n = read::<usize>(); let a = read_vec::<usize>(); let mut poses = vec![vec![]; 150001]; for (i, &num) in a.iter().enumerate() { poses[num].push(i); } for i in 0..150001 { if poses[i].len() >= 2 { let mut answers = vec![0; n]; answers[poses[i][0]] = i as i64; answers[poses[i][1]] = -(i as i64); yes(&answers); return; } } let max_search = 17; let mut cand_pos = vec![]; let mut cand_num = vec![]; for i in 0..150001 { if poses[i].len() == 1 { cand_num.push(i as i64); cand_pos.push(poses[i][0]); } if cand_num.len() == max_search { break; } } let mut dp = HashSet::new(); let mut from = HashMap::new(); for i in 0..cand_num.len() { let mut new = vec![]; for &num in &dp { if !dp.contains(&(cand_num[i] + num)) { from.insert(cand_num[i] + num, (Some(num), i, 1)); new.push(cand_num[i] + num); } if !dp.contains(&(-cand_num[i] + num)) { from.insert(-cand_num[i] + num, (Some(num), i, -1)); new.push(-cand_num[i] + num); } } if !dp.contains(&cand_num[i]) { from.insert(cand_num[i], (None, i, 1)); new.push(cand_num[i]); } if !dp.contains(&(-cand_num[i])) { from.insert(-cand_num[i], (None, i, -1)); new.push(-cand_num[i]); } for num in new { dp.insert(num); } } if dp.contains(&0) { let mut cur = 0; let mut answers = vec![0; n]; loop { let (prev, idx, sign) = from[&cur]; let i = cand_pos[idx]; answers[i] = a[i] as i64 * sign; if let Some(p) = prev { cur = p; } else { break; } } yes(&answers); } else { println!("No"); } } fn read<T: std::str::FromStr>() -> T { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); s.trim().parse().ok().unwrap() } fn read_vec<T: std::str::FromStr>() -> Vec<T> { read::<String>() .split_whitespace() .map(|e| e.parse().ok().unwrap()) .collect() }