結果
問題 | No.3143 Colorless Green Parentheses Sleep Furiously |
ユーザー |
👑 |
提出日時 | 2025-05-16 22:23:29 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 8 ms / 2,000 ms |
コード長 | 2,778 bytes |
コンパイル時間 | 927 ms |
コンパイル使用メモリ | 113,132 KB |
実行使用メモリ | 8,896 KB |
最終ジャッジ日時 | 2025-05-17 00:31:02 |
合計ジャッジ時間 | 2,968 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 49 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:64:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 64 | scanf("%s", S); | ~~~~~^~~~~~~~~
ソースコード
#include <cassert> #include <cmath> #include <cstdint> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <bitset> #include <chrono> #include <complex> #include <deque> #include <functional> #include <iostream> #include <limits> #include <map> #include <numeric> #include <queue> #include <random> #include <set> #include <sstream> #include <string> #include <unordered_map> #include <unordered_set> #include <utility> #include <vector> using namespace std; using Int = long long; template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; }; template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; } template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; } template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; } template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; } #define COLOR(s) ("\x1b[" s "m") int N, K; char S[200'010]; vector<int> us, to; string ans; int parse(int l, int r, int p) { int ret = 0; for (int x = l; x < r; x = to[x] + 1) { const int u = us[x]; if (ans.size() && (ans.back() == ')' || ans.back() == '1')) ans += "+"; ans += "("; int res = parse(x + 1, to[x], u); for (; res < 2; ++res) { if (ans.size() && (ans.back() == ')' || ans.back() == '1')) ans += "+"; ans += "1"; } ans += ")"; ret += 1; } return ret; } int main() { for (; ~scanf("%d%d", &N, &K); ) { scanf("%s", S); us.assign(N, -1); to.assign(N, -1); if ([&]() -> bool { vector<int> stack; int u = 0; for (int x = 0; x < N; ++x) { if (S[x] == '(') { stack.push_back(x); us[x] = u++; } else { if (!stack.size()) return false; const int y = stack.back(); stack.pop_back(); to[y] = x; to[x] = y; } } if (stack.size()) return false; return true; }()) { ans = ""; int res = parse(0, N, -1); for (; res < 2; ++res) { if (ans.size() && (ans.back() == ')' || ans.back() == '1')) ans += "+"; ans += "1"; } // cerr<<"ans = "<<ans<<endl; int cnt1 = count(ans.begin(), ans.end(), '1'); if (cnt1 <= K) { for (; cnt1 < K; ++cnt1) ans += "+1"; puts("Yes"); puts(ans.c_str()); } else { puts("No"); } } else { puts("No"); } } return 0; }