fork(1) download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <cmath>
  5.  
  6. using namespace std;
  7.  
  8. const int MAX_LENGTH = 100000; // Maximum input length
  9.  
  10. // Compute prefix balance array: balance[i] = net open brackets up to i
  11. vector<int> computePrefixBalance(const string& s) {
  12.     int n = s.length();
  13.     vector<int> balance(n);
  14.     int currBalance = 0;
  15.     for (int i = 0; i < n; ++i) {
  16.         if (s[i] == '(') {
  17.             currBalance += 1;
  18.         } else {
  19.             currBalance -= 1;
  20.         }
  21.         balance[i] = currBalance;
  22.     }
  23.     return balance;
  24. }
  25.  
  26. // Check if the string becomes valid after flipping bracket at position idx
  27. bool isValidAfterFlip(const string& s, int idx, const vector<int>& prefixBalance, int n) {
  28.     // Flipping '(' -> ')' decreases balance by 2
  29.     // Flipping ')' -> '(' increases balance by 2
  30.     int delta = 0;
  31.     if (s[idx] == '(') {
  32.         delta = -2;
  33.     } else {
  34.         delta = 2;
  35.     }
  36.  
  37.     int currBalance = 0;
  38.     int minBalance = 0;
  39.  
  40.     // Prefix before idx
  41.     if (idx > 0) {
  42.         currBalance = prefixBalance[idx - 1];
  43.         if (currBalance < minBalance) {
  44.             minBalance = currBalance;
  45.         }
  46.     }
  47.  
  48.     // Apply flip at idx
  49.     currBalance += delta;
  50.     if (currBalance < minBalance) {
  51.         minBalance = currBalance;
  52.     }
  53.  
  54.     // Process suffix (from idx+1 to end)
  55.     if (idx < n - 1) {
  56.         int suffixBalance = prefixBalance[n - 1] - prefixBalance[idx];
  57.         currBalance += suffixBalance;
  58.         if (currBalance < minBalance) {
  59.             minBalance = currBalance;
  60.         }
  61.     }
  62.  
  63.     // Valid if final balance = 0 and never negative
  64.     if (currBalance == 0 && minBalance >= 0) {
  65.         return true;
  66.     } else {
  67.         return false;
  68.     }
  69. }
  70.  
  71. // Validate input
  72. bool isValidInput(const string& s) {
  73.     int n = s.length();
  74.     if (n < 1 || n > MAX_LENGTH) {
  75.         return false;
  76.     }
  77.     if (n % 2 != 0) {
  78.         return false; // Odd length can't form valid parentheses
  79.     }
  80.     for (char c : s) {
  81.         if (c != '(' && c != ')') {
  82.             return false;
  83.         }
  84.     }
  85.     return true;
  86. }
  87.  
  88. // Count valid sequences obtainable by flipping exactly one bracket
  89. int countValidFlips(const string& s) {
  90.     if (!isValidInput(s)) {
  91.         return 0;
  92.     }
  93.  
  94.     int n = s.length();
  95.     vector<int> prefixBalance = computePrefixBalance(s);
  96.  
  97.     // For a single flip to fix the sequence, final balance must be ±2
  98.     int finalBalance = prefixBalance[n - 1];
  99.     if (abs(finalBalance) != 2) {
  100.         return 0;
  101.     }
  102.  
  103.     int validCount = 0;
  104.     for (int i = 0; i < n; ++i) {
  105.         if (isValidAfterFlip(s, i, prefixBalance, n)) {
  106.             validCount += 1;
  107.         }
  108.     }
  109.     return validCount;
  110. }
  111.  
  112. int main() {
  113.     ios_base::sync_with_stdio(false);
  114.     cin.tie(nullptr);
  115.  
  116.     string s;
  117.     cin >> s;
  118.     cout << countValidFlips(s) << '\n';
  119.     return 0;
  120. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/260exL
language:
C++ (gcc 8.3)
created:
16 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!