結果

問題 No.3143 Colorless Green Parentheses Sleep Furiously
ユーザー magurofly
提出日時 2025-05-16 21:56:58
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 13 ms / 2,000 ms
コード長 4,948 bytes
コンパイル時間 11,201 ms
コンパイル使用メモリ 400,664 KB
実行使用メモリ 10,148 KB
最終ジャッジ日時 2025-05-17 00:26:38
合計ジャッジ時間 13,979 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 49
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused variable: `N`
 --> src/main.rs:5:7
  |
5 |       N: usize, K: usize,
  |       ^ help: if this is intentional, prefix it with an underscore: `_N`
  |
  = note: `#[warn(unused_variables)]` on by default

ソースコード

diff # 

#![allow(dead_code, unused_imports, unused_macros, non_snake_case)]

fn main() {
    input! {
      N: usize, K: usize,
      S: Chars,
    }
    
    let mut level = 0_i32;
    let mut stack = vec![];
    let mut nodes = vec![vec![]];
    let mut current = 0;
    for c in S {
      match c {
        '(' => {
          level += 1;
          stack.push(current);
          let inner = nodes.len();
          nodes.push(vec![]);
          nodes[current].push(inner);
          current = inner;
        }
        ')' => {
          level -= 1;
          if level < 0 {
            no();
            return;
          }
          current = stack.pop().unwrap();
        }
        _ => unreachable!()
      }
    }

    if level != 0 {
      no();
      return;
    }

    fn dfs(ans: &mut String, nodes: &[Vec<usize>], current: usize) -> usize {
      let mut min = 0;
      match nodes[current].len() {
        0 => {
          ans.push_str("1+1");
          min += 2;
        }
        1 => {
          ans.push('(');
          min += dfs(ans, nodes, nodes[current][0]);
          ans.push_str(")+1");
          min += 1;
        }
        _ => {
          ans.push('(');
          min += dfs(ans, nodes, nodes[current][0]);
          for &inner in &nodes[current][1 ..] {
            ans.push_str(")+(");
            min += dfs(ans, nodes, inner);
          }
          ans.push(')');
        }
      }
      min
    }

    let mut ans = String::new();
    let min = dfs(&mut ans, &nodes, current);
    if min > K {
      no();
      return;
    }
    yes();
    for _ in 0 .. K - min {
      ans.push_str("+1");
    }
    say(ans);
}

type Int = i64;
const MOD: Int = 998244353;
// const MOD: Int = 1_000_000_007;
const INF: Int = 1_000_000_000_000_000_000;
const YESNO: [&'static str; 2] = ["Yes", "No"];

use proconio::{input, input_interactive, marker::{Chars, Bytes, Usize1}};
use std::*;
use std::ops::*;
use collections::*; // (BTree|Hash)(Set|Map), BinaryHeap, VecDeque, LinkedList
use cmp::{self, Reverse}; // cmp::{min, max}

fn yes() { println!("{}", YESNO[0]); }
fn no() { println!("{}", YESNO[1]); }
fn yesno(c: bool) { println!("{}", if c { YESNO[0] } else { YESNO[1] }); }
fn say<T: std::fmt::Display>(x: T) -> T { println!("{}", x); x }
fn neighbor4<F: FnMut(usize, usize)>(i: usize, j: usize, h: usize, w: usize, mut f: F) { if i > 0 { (f)(i - 1, j); } if i < h - 1 { (f)(i + 1, j); } if j > 0 { (f)(i, j - 1); } if j < w - 1 { (f)(i, j + 1); } }

trait MyItertools : Iterator + Sized {
  fn to_vec(self) -> Vec<Self::Item> { self.collect::<Vec<_>>() }
  fn to_vec_rev(self) -> Vec<Self::Item> { let mut v = self.collect::<Vec<_>>(); v.reverse(); v }
  fn tally(self) -> HashMap<Self::Item, usize> where Self::Item: Copy + Eq + hash::Hash { let mut counts = HashMap::new(); self.for_each(|item| *counts.entry(item).or_default() += 1 ); counts }
  fn count_if<P: Fn(Self::Item) -> bool>(self, predicate: P) -> usize { self.map(predicate).filter(|&x| x ).count() }
  fn implode(self, sep: &str) -> String where Self::Item: std::string::ToString { self.map(|x| x.to_string()).to_vec().join(sep) }
  fn mex(self, gen: impl IntoIterator<Item = Self::Item>) -> Self::Item where Self::Item: Ord { let mut v = self.collect::<Vec<_>>(); v.sort(); v.dedup(); let mut it = v.into_iter(); gen.into_iter().find(|a| if let Some(x) = it.next() { a != &x } else { true }).unwrap() }
}
impl<T: ?Sized> MyItertools for T where T: Iterator + Sized {}

trait MyOrd : PartialOrd + Sized {
  fn chmax(&mut self, mut rhs: Self) -> bool { if self < &mut rhs { *self = rhs; true } else { false } }
  fn chmin(&mut self, mut rhs: Self) -> bool { if self > &mut rhs { *self = rhs; true } else { false } }
}
impl<T: Sized + PartialOrd> MyOrd for T {}

#[derive(Debug, Clone, Default)]
pub struct BTreeMultiset<T: Ord> { len: usize, set: BTreeMap<T, usize> }
impl<'a, T: Ord> BTreeMultiset<T> {
  pub fn new() -> Self { Self { len: 0, set: BTreeMap::new() } }
  pub fn len(&self) -> usize { self.len }
  pub fn count(&self, x: &T) -> usize { self.set.get(x).copied().unwrap_or(0) }
  pub fn insert_multiple(&mut self, x: T, count: usize) -> usize { self.len += count; let n = self.set.entry(x).or_insert(0); *n += count; *n }
  pub fn insert(&mut self, x: T) -> usize { self.insert_multiple(x, 1) }
  pub fn remove_multiple(&mut self, x: &T, count: usize) -> usize { if let Some(n) = self.set.get_mut(x) { let n0 = *n; *n = n0.saturating_sub(count); let n = *n; self.len -= n0 - n; if n == 0 { self.set.remove(x); } n } else { 0 } }
  pub fn remove(&mut self, x: &T) -> usize { self.remove_multiple(x, 1) }
  pub fn iter(&'a self) -> btree_map::Iter<'a, T, usize> { self.set.iter() }
  pub fn into_iter(self) -> btree_map::IntoIter<T, usize> { self.set.into_iter() }
  pub fn keys(&'a self) -> btree_map::Keys<'a, T, usize> { self.set.keys() }
  pub fn range(&'a self, range: impl RangeBounds<T>) -> btree_map::Range<'a, T, usize> { self.set.range(range) }
}
0