結果

問題 No.3143 Colorless Green Parentheses Sleep Furiously
ユーザー Leal-0
提出日時 2025-05-17 16:22:54
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,627 bytes
コンパイル時間 2,502 ms
コンパイル使用メモリ 204,272 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-05-17 16:23:06
合計ジャッジ時間 10,362 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 2
other AC * 10 WA * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifndef INCLUDED_MAIN
#define INCLUDED_MAIN

#include __FILE__


int main(){

    ll n,k;
    cin>>n>>k;
    string s;
    cin>>s;

    if(!taio(s)){
        no();
        return 0;
    }
    if(calc_min(s)<k) {
        no();
        return 0;
    }

    vector<int> match(n, 1);
    stack<int> st;
    rep(i,n){
        if(s[i]=='(') st.push(i);
        else {
            int j=st.top();
            st.pop();
            match[i]=j;
            match[j]=i;
        }
    }

    string ans="";
    stack<int> waiting;
    rep(i,n) {
        char cc=s[i];
        if(cc=='(') {
            waiting.push(i);
            ans+=cc;
        }
        else {
            int left=waiting.top();
            waiting.pop();
            if(left==i-1) {
                ans+="1+1)";
            }
            else ans+=')';
            if(i<n-1 && s[i+1]=='(') ans+="+";
            if(i<n-1 && s[i+1]==')' && match[i+1]==left-1) {
                ans+="+1";
            }
        }
    }
       
    if(ans[0]=='(' && ans.back()==')' && match[0]==n-1) ans+="+1";


    ll mn=calc_min(s);
    while(mn<k){
        ans+="+1";
        mn++;
    }
    yes();
    cout<<ans<<"\n";
    return 0;
}


/////// library zone ///////
#else
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define srep(i,l,r) for(ll i=l;i<=r;i++)
using ll = long long;
using ld = long double;
const ll mod=998244353;
#define vout(v) for(auto i :v) cout<<i<<" ";
#define INF 9223300000000000000ll
#define Winf 5e12
#define nl "\n"
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define vl vector<ll>
#define vc vector<char>



ll calc_min(const string &s){
    stack<ll> st;
    for(char c:s){
        if(c=='('){
            st.push(0);
        } else {
            ll cur=st.top(); st.pop();
            ll sc=(cur==0 ? 2 : cur+1);
            if(st.empty()) st.push(sc);
            else{
                ll t=st.top(); st.pop();
                st.push(t+sc);
            }
        }
    }
    return st.empty()?0:st.top();
}

bool taio(const string &s){
    ll bal=0;
    for(char c:s){
        if(c=='(') bal++;
        else{
            if(bal==0) return false;
            bal--;
        }
    }
    return bal==0;
}


template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}

void no() { cout<<"No"<<nl;}
void yes() { cout<<"Yes"<<nl;}
void yn(bool a) {
    cout<<(a ? "Yes":"No")<<nl;
}

ll sum(vector<ll>& a) {
    ll ans=0;
    for(auto i:a) ans+=i;
    return ans;
}

#endif
0