Submission #13093435

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,b,a) for(ll i=b;i>=a;i--)
#define fori(a) for(auto i : a )
#define all(a) begin(a), end(a)
#define set(a,b) memset(a,b,sizeof(a))
#define sz(a) a.size()
#define pi 3.14159
#define ll long long
#define ull unsigned long long
#define pb push_back
#define PF push_front //deque
#define mp make_pair
#define pq priority_queue
#define mod 1000000007
#define f first
#define s second
#define pii pair< ll, ll >
#define vi vector<ll>
#define vpii vector<pii>
#define debug(v) for(auto i:v) cout<<i<<" ";
#define tc ll t; cin >> t; while(t--)

using namespace std;
string repeat(string s, ll n) {
    string s1 = "";
    for (ll i=0; i<n;i++)
        s1+=s;
    return s1;
}
string getString(char x) {
    string s(1, x);
    return s;
}

void optimizeIO(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
ll gcd(ll a, ll b){
    if (a == 0)  return b;
    return gcd(b % a, a);
}
void solve(){
  ll n;
  cin>>n;
  vector<string> s(n);
  string g;
  rep(i,0,n) {cin>>g; s[i]=g;}
  vector<pii> v1(n,{0,0});
  vector<ll> op,clos;
  vpii op_clos;
  rep(i,0,n){
    stack<ll> st;
    g=s[i];
    rep(j,0,(ll)g.length()){
      if(st.empty()){
        if(g[j]=='(') st.push(1);
        else st.push(-1);
      }
      else{
        if(g[j]=='('){
          if(st.top()<0) st.push(1);
          else{
            ll x=st.top();
            st.pop();
            st.push(x+1);
          }
        }
        else{
          ll x=st.top();
          x--;
          st.pop();
          if(x!=0) st.push(x);
        }
      }

    }
    ll mn=0,mx=0;
    while(!st.empty()){
      if(st.top()<0) mn=st.top();
      if(st.top()>0) mx=st.top();
      st.pop();
    }
    v1[i]={mn,mx};
    if(mn==0 && mx>0){
      op.push_back(i);
    }
    else if(mx==0 && mn<0){
      clos.pb(i);
    }
    else if(mx>0 && mn<0){
      op_clos.pb({mn,mx});
    }
  }

  ll op1=0,flag=0;
  rep(i,0,(ll)op.size()){
    op1+=v1[op[i]].s;
  }
  auto comp=[](pii &x,pii &y){
    return (x.f+x.s)>(y.f+y.s);
  };
  sort(all(op_clos),comp);
  rep(i,0,(ll)op_clos.size()){
    pii x=op_clos[i];
    if(op1<abs(x.f)) {flag=1; break;}
    else{
      op1+=x.f;
      op1+=x.s;
    }
  }
  // cout<<flag<<endl;
  rep(i,0,(ll)clos.size()){
    pii x=v1[clos[i]];
    if(op1<abs(x.f)){flag=1; break;}
    else op1+=x.f;
  }
  // cout<<op1<<endl;
  if(op1!=0) flag=1;
  if(flag) cout<<"No\n";
  else cout<<"Yes\n";
}
int main(){
    optimizeIO();

    solve();

}

Submission Info

Judge Result