結果
問題 | No.873 バイナリ、ヤバいなり!w |
ユーザー |
|
提出日時 | 2022-12-06 18:29:46 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 268 ms / 2,000 ms |
コード長 | 1,672 bytes |
コンパイル時間 | 12,538 ms |
コンパイル使用メモリ | 401,832 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-07 01:50:43 |
合計ジャッジ時間 | 16,038 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
コンパイルメッセージ
warning: unused import: `fmt::format` --> src/main.rs:1:48 | 1 | use std::{collections::{VecDeque, BinaryHeap}, fmt::format, cmp::Reverse}; | ^^^^^^^^^^^ | = note: `#[warn(unused_imports)]` on by default
ソースコード
use std::{collections::{VecDeque, BinaryHeap}, fmt::format, cmp::Reverse};const INF: usize = 1usize << 60;fn priority(val: usize) -> usize {if val % 2 == 1 {val} else {INF - val}}fn main() {let mut n = String::new();std::io::stdin().read_line(&mut n).ok();let n: usize = n.trim().parse().unwrap();let mut dp = vec![INF; n+1];dp[0] = 0;for i in 1..=n {for j in 1..=i {let val = j * j;if val > i { break; }dp[i] = dp[i].min(dp[i-val] + j);}}let mut uses = vec![];let mut target = n;while target > 0 {let mut pque = BinaryHeap::new();for i in 1.. {let val = i * i;if val > target { break; }if dp[target] == dp[target-val] + i {pque.push((Reverse(priority(i)), i));}}let (_, val) = pque.pop().unwrap();uses.push(val);target -= val * val;}uses.sort();let odds = uses.iter().filter(|&&v| v % 2 == 1).copied().collect::<Vec<_>>();let mut evens = uses.iter().filter(|&&v| v % 2 == 0).copied().collect::<VecDeque<_>>();let mut result = String::new();for &v in odds.iter() {let val = format!("0{}", "10".repeat(v/2));result.push_str(&val);}let limit = evens.len();for i in 0..limit {let val = if i % 2 == 0 { evens.pop_back().unwrap() } else { evens.pop_front().unwrap() };let val = format!("{}", if i % 2 == 0 { "01".repeat(val/2) } else { "10".repeat(val/2) });result.push_str(&val);}println!("{}", result);}