Submission #1698740

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  string s;
  cin >> s;

  int dist1 = 0, dist2 = 0;
  int ans = 0;
  queue<int> que;
  int cnt = 0;
  for(int i=0;i<s.size();i++) {
    if(s[i] == '(')
      cnt++;
    else {
      que.push(i);
      cnt--;
    }
    if(cnt < 0) {
      dist1 = que.front();
      que.pop();
      s[dist1] = '(';
      cnt += 2;
      ans++;
    }
  }
  vector<int> v(s.size(), 0);
  cnt = 0;
  for(int i=0;i<s.size();i++) {
    if(s[i] == '(')
      cnt++;
    else
      cnt--;
    v[i] = cnt;
  }
  if(v[s.size()-1] > 0) {
    int opn = v[s.size()-1] / 2;
    int idx = s.size() - 1;
    while(idx > 0) {
      if(v[idx-1] >= 2 * opn)
        idx--;
      else
        break;
    }
    cout << ans + idx + opn << endl;
  } else {
    cout << ans + dist1 << endl;
  }


}

Submission Info

Judge Result