Submission #62307518

---

Source Code Expand

#[allow(unused_imports)]
use itertools::Itertools;
use proconio::input;
use proconio::marker::Chars;

struct Node {
    color: char,
    cost: i32,
}

impl Node {
    fn new(color: char, cost: i32) -> Self {
        Self { color, cost }
    }

    fn vote(v: &Vec<Node>) -> (char, i32) {
        let col = if v.iter().filter(|c| c.color == '0').count() >= 2 {
            '0'
        } else {
            '1'
        };
        let other = if col == '0' {
            '1'
        } else {
            '0'
        };
        let c = col;
        let cost = v.iter()
            .map(|c| if c.color == other { 0 } else { c.cost })
            .sorted_unstable()
            .enumerate()
            .map(|(i, c)| if i == 2 { 0 } else { c })
            .sum::<i32>();
        (c, cost)
    }
}

fn dfs(i: usize, n: usize, offset: usize, s: &Vec<char>) -> Node {
    if i == n {
        return Node::new(s[offset], 1);
    }

    let k = s.len() / 3usize.pow(i as u32+1);
    let mut v = vec![];
    for j in 0..3 {
        v.push(dfs(i+1, n, offset + k*j, s));
    }
    let (c, cost) = Node::vote(&v);
    Node::new(c, cost)
}

fn main() {
    input!{
        n: usize,
        s: Chars,
    }
    let res = dfs(0, n, 0, &s);
    println!("{}", res.cost);
}

pub trait Debuggable {
    fn debug_string(&self) -> String;
}

impl<T: std::fmt::Debug + std::fmt::Display> Debuggable for Vec<T> {
    fn debug_string(&self) -> String {
        use itertools::Itertools;
        use std::iter::repeat;
        if let Some(max_size) = self.iter()
            .enumerate()
            .map(|(i, x)| (format!("{:?}", x).len()).max(format!("{:?}", i).len()))
            .max() {
                let mut idx = String::from("idx |");   
                let mut val = String::from("val |");   
                for (i, xi) in self.iter().enumerate() {
                    idx.push_str(
                        &format!(" {:>w$} |", i, w=max_size)
                    );
                    val.push_str(
                        &format!(" {:>w$} |", xi, w=max_size)
                    );
                }

                format!("{}\n{}\n{}\n", idx, repeat('-').take(idx.len()).join(""), val)
            } else {
                format!("idx | \nval |\n")
            }
    }
}

impl<T: std::fmt::Debug + std::fmt::Display> Debuggable for std::collections::BTreeSet<T> {
    fn debug_string(&self) -> String {
        use itertools::Itertools;
        format!("{{ {} }}", self.iter().join(", "))
    }
}

impl<T, U> Debuggable for std::collections::BTreeMap<T, U> 
where T: std::fmt::Debug + std::fmt::Display, U: std::fmt::Debug + std::fmt::Display
{
    fn debug_string(&self) -> String {
        use itertools::Itertools;
        format!(
            "{{\n{}\n }}", self.iter()
                .map(|(k, v)| format!("{k} -> {v}, "))
                .join("\n")
        )
    }
}

// lg! マクロの定義
#[macro_export]
macro_rules! lg {
    ($val:expr) => {
        #[cfg(feature = "local")]
        {
            {
                use Debuggable;
                let val = &$val;
                eprintln!(
                    "[{}:{}] {} = \n{}",
                    file!(),
                    line!(),
                    stringify!($val),
                    val.debug_string()
                );
                val
            }
        }
    }
}
    

Submission Info

Compile Error

warning: the item `Itertools` is imported redundantly
  --> src/main.rs:67:13
   |
2  | use itertools::Itertools;
   |     -------------------- the item `Itertools` is already imported here
...
67 |         use itertools::Itertools;
   |             ^^^^^^^^^^^^^^^^^^^^
   |
   = note: `#[warn(unused_imports)]` on by default

warning: the item `Itertools` is imported redundantly
  --> src/main.rs:93:13
   |
2  | use itertools::Itertools;
   |     -------------------- the item `Itertools` is already imported here
...
93 |         use itertools::Itertools;
   |             ^^^^^^^^^^^^^^^^^^^^

warning: the item `Itertools` is imported redundantly
   --> src/main.rs:102:13
    |
2   | use itertools::Itertools;
    |     -------------------- the item `Itertools` is already imported here
...
102 |         use itertools::Itertools;
    |             ^^^^^^^^^^^^^^^^^^^^

Judge Result