結果

問題 No.3143 Colorless Green Parentheses Sleep Furiously
ユーザー sai
提出日時 2025-05-16 22:31:24
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,638 bytes
コンパイル時間 3,344 ms
コンパイル使用メモリ 279,048 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2025-05-17 00:32:56
合計ジャッジ時間 10,558 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20 WA * 1 RE * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

void check(const int n, const int k, const std::string &s, const std::string &ans) {
  {
    int id = 0;
    for (auto c : ans) {
      if (s[id] == c) {
        id++;
        if (id == n) {
          break;
        }
      }
    }
    if (id < n) {
      assert(false);
    }
  }
  {
    int cnt = 0;
    for (auto c : ans) {
      cnt += c == '1';
    }
    assert(cnt == k);
  }
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n, k;
  std::string s;
  std::cin >> n >> k >> s;
  int Min = 0;
  int cnt = 0, Max = 0;
  for (int i = 0; i < n; i++) {
    if (s[i] == '(') {
      cnt++;
      Max++;
    } else {
      if (cnt == 0) {
        std::cout << "No\n";
        return 0;
      }
      cnt--;
      if (cnt == 0) {
        Min += Max + 1;
        Max = 0;
      }
    }
  }
  if (cnt > 0 || Min > k) {
    std::cout << "No\n";
    return 0;
  }
  std::cout << "Yes\n";
  std::vector<int> Pair(n, -1), st;
  for (int i = 0; i < n; i++) {
    if (s[i] == '(') {
      st.push_back(i);
    } else {
      assert(st.size());
      Pair[st.back()] = i;
      Pair[i] = st.back();
      st.pop_back();
    }
  }
  assert(st.empty());
  std::string ans = "";
  for (int i = 0; i < n; i++) {
    if (s[i] == '(') {
      if (i > 0 && s[i - 1] == ')') {
        ans += '+';
      }
      ans += '(';
      if (Pair[i] == i + 1) {
        ans += "1+1";
      }
      if (s.substr(i + 1, 2) == "()") {
        ans += "1+";
      }
    } else {
      ans += ')';
    }
  }
  for (int i = k - Min; i--;) {
    ans += "+1";
  }
  check(n, k, s, ans);
  std::cout << ans << '\n';
}
0