結果

問題 No.3143 Colorless Green Parentheses Sleep Furiously
ユーザー Leal-0
提出日時 2025-05-16 23:01:50
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,198 bytes
コンパイル時間 2,047 ms
コンパイル使用メモリ 213,300 KB
実行使用メモリ 20,348 KB
最終ジャッジ日時 2025-05-17 00:34:58
合計ジャッジ時間 11,789 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 43 RE * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifndef INCLUDED_MAIN
#define INCLUDED_MAIN

#include __FILE__

int main(){

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

    vector<int> st;
    vector<int> match(n,-1);
    rep(i,n){
        if(s[i]=='(') st.push_back(i);
        else{
            int j=st.back(); st.pop_back();
            match[i]=j; match[j]=i;
        }
    }

    int root=0;
    st.clear();
    vector<int> id(n,-1);
    int tid=0;
    rep(i,n) if(s[i]=='(') id[i]=tid++;
    vector<int> p(tid,-1);
    rep(i,n){
        if(s[i]=='(') st.push_back(i);
        else{
            int op=match[i];
            int cid=id[op];
            st.pop_back();
            if(!st.empty()){
                int pop=st.back();
                int pid=id[pop];
                p[cid]=pid;
            } else root=cid;
        }
    }

    vector<vector<int>> children(tid);
    rep(i,tid)  if(p[i]>=0) children[p[i]].push_back(i);

    vector<ll> fmin(tid,0), x(tid,0);
    function<bool(int)> dfs=[&](int u){
        ll sumc=0;
        for(int v:children[u]){
            if(!dfs(v)) return false;
            sumc+=fmin[v];
        }
        int sc=(int)children[u].size();
        ll minn=(sc>=2?0:2-sc);
        fmin[u]=sumc+minn;
        x[u]=minn;
        return true;
    };

    if(!dfs(root)||fmin[root]>k){
        no();
        return 0;
    }

    x[root]+=k-fmin[root];

    function<string(int)> build=[&](int u){
        vector<string> items;
        for(int v:children[u]) items.push_back(build(v));
        for(int i=0;i<x[u];i++) items.push_back("1");
        string res="(";
        rep(i,(int)items.size()){
            if(i) res+="+";
            res+=items[i];
        }
        res+=")";
        return res;
    };

    yes();
    cout<<build(root)<<nl;
    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