結果
問題 | No.1017 Reiwa Sequence |
ユーザー | fukafukatani |
提出日時 | 2020-04-03 23:12:44 |
言語 | Rust (1.77.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,917 bytes |
コンパイル時間 | 3,421 ms |
コンパイル使用メモリ | 161,236 KB |
実行使用メモリ | 153,736 KB |
最終ジャッジ日時 | 2023-09-16 04:34:00 |
合計ジャッジ時間 | 27,148 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
5,320 KB |
testcase_01 | AC | 3 ms
5,304 KB |
testcase_02 | AC | 4 ms
5,372 KB |
testcase_03 | AC | 6 ms
6,048 KB |
testcase_04 | AC | 3 ms
5,320 KB |
testcase_05 | AC | 4 ms
5,312 KB |
testcase_06 | AC | 4 ms
5,304 KB |
testcase_07 | AC | 4 ms
5,288 KB |
testcase_08 | AC | 3 ms
5,308 KB |
testcase_09 | AC | 103 ms
41,936 KB |
testcase_10 | AC | 477 ms
78,292 KB |
testcase_11 | AC | 45 ms
23,920 KB |
testcase_12 | AC | 645 ms
150,516 KB |
testcase_13 | AC | 462 ms
78,152 KB |
testcase_14 | AC | 40 ms
22,612 KB |
testcase_15 | AC | 100 ms
41,740 KB |
testcase_16 | AC | 45 ms
22,616 KB |
testcase_17 | AC | 579 ms
153,208 KB |
testcase_18 | AC | 44 ms
22,648 KB |
testcase_19 | AC | 926 ms
153,488 KB |
testcase_20 | AC | 755 ms
150,532 KB |
testcase_21 | AC | 717 ms
150,472 KB |
testcase_22 | AC | 671 ms
151,140 KB |
testcase_23 | AC | 588 ms
149,964 KB |
testcase_24 | AC | 472 ms
150,228 KB |
testcase_25 | AC | 402 ms
153,736 KB |
testcase_26 | AC | 256 ms
77,504 KB |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | AC | 775 ms
150,524 KB |
testcase_30 | WA | - |
testcase_31 | AC | 579 ms
149,800 KB |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | AC | 3 ms
5,300 KB |
testcase_35 | AC | 4 ms
5,340 KB |
testcase_36 | AC | 3 ms
5,304 KB |
testcase_37 | WA | - |
testcase_38 | WA | - |
testcase_39 | WA | - |
testcase_40 | AC | 25 ms
10,968 KB |
testcase_41 | AC | 25 ms
10,892 KB |
testcase_42 | AC | 24 ms
10,592 KB |
testcase_43 | AC | 24 ms
10,756 KB |
testcase_44 | AC | 24 ms
10,920 KB |
testcase_45 | AC | 24 ms
10,780 KB |
testcase_46 | AC | 24 ms
10,700 KB |
testcase_47 | AC | 23 ms
10,588 KB |
testcase_48 | AC | 41 ms
11,116 KB |
testcase_49 | AC | 35 ms
13,760 KB |
testcase_50 | AC | 25 ms
8,932 KB |
testcase_51 | AC | 3 ms
5,296 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 = 15; 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() }