結果
問題 | No.873 バイナリ、ヤバいなり!w |
ユーザー |
|
提出日時 | 2021-11-13 17:49:10 |
言語 | Rust (1.83.0 + proconio) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,170 bytes |
コンパイル時間 | 14,964 ms |
コンパイル使用メモリ | 378,744 KB |
実行使用メモリ | 11,264 KB |
最終ジャッジ日時 | 2024-06-11 14:09:45 |
合計ジャッジ時間 | 17,539 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 WA * 1 |
ソースコード
#[allow(unused_imports)]use std::cmp::*;#[allow(unused_imports)]use std::collections::*;use std::io::Read;#[allow(dead_code)]fn getline() -> String {let mut ret = String::new();std::io::stdin().read_line(&mut ret).ok().unwrap();ret}fn get_word() -> String {let stdin = std::io::stdin();let mut stdin=stdin.lock();let mut u8b: [u8; 1] = [0];loop {let mut buf: Vec<u8> = Vec::with_capacity(16);loop {let res = stdin.read(&mut u8b);if res.unwrap_or(0) == 0 || u8b[0] <= b' ' {break;} else {buf.push(u8b[0]);}}if buf.len() >= 1 {let ret = String::from_utf8(buf).unwrap();return ret;}}}#[allow(dead_code)]fn get<T: std::str::FromStr>() -> T { get_word().parse().ok().unwrap() }fn main() {let n: usize = get();const INF: usize = 1 << 20;let mut dp = vec![(INF, 0); n + 1];let mut dpe = vec![(INF, 0); n + 1];dp[0] = (0, 0);for i in 1..275 {let v = 2 * i;for j in v * v..n + 1 {let (p, _) = dp[j - v * v];dp[j] = min(dp[j], (p + v, v));}}for i in (0..275).rev() {let v = 2 * i + 1;for j in v * v..n + 1 {let (p, _) = dp[j - v * v];dp[j] = min(dp[j], (p + v, v));}}dpe[0] = (0, 0);for i in (1..275).rev() {let v = 2 * i;for j in v * v..n + 1 {let (p, _) = dpe[j - v * v];dpe[j] = min(dpe[j], (p + v, v));}}let mut path = vec![];let mut cur = n;let mut even = false;while cur > 0 {let t = if even { dpe[cur].1 } else { dp[cur].1 };if even {assert_eq!(dpe[cur].0, dp[cur].0);}path.push(t);cur -= t * t;if t % 2 == 0 {even = !even;}}eprintln!("path = {:?}", path);let mut bias = 0;for v in path {for i in 0..v {print!("{}", (i + bias) % 2);}bias += v + 1;}println!();}