fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <climits>
  5.  
  6. using namespace std;
  7.  
  8. // Checks if the input string is valid: contains only '(' and ')', and length is within bounds
  9. bool isValidInput(const string& s) {
  10.     const int MAX_LENGTH = 100000;
  11.     if (s.empty() || s.size() > MAX_LENGTH) {
  12.         return false;
  13.     }
  14.     for (char c : s) {
  15.         if (c != '(' && c != ')') {
  16.             return false;
  17.         }
  18.     }
  19.     return true;
  20. }
  21.  
  22. // Checks if flipping the parenthesis at position pos results in a valid sequence
  23. bool isValidAfterFlip(const string& s, int pos) {
  24.     int n = s.size();
  25.     int balance = 0;
  26.  
  27.     // Simulate balance for the entire string after flipping
  28.     for (int i = 0; i < n; ++i) {
  29.         if (i == pos) {
  30.             balance += (s[i] == '(' ? -1 : 1); // Flip '(' to ')' (-1), ')' to '(' (+1)
  31.         } else {
  32.             balance += (s[i] == '(' ? 1 : -1); // Normal contribution
  33.         }
  34.         if (balance < 0) { // Invalid if balance goes negative
  35.             return false;
  36.         }
  37.     }
  38.     return balance == 0; // Valid sequence must end with balance = 0
  39. }
  40.  
  41. // Counts the number of valid sequences by flipping exactly one parenthesis
  42. int countValidFlips(const string& s) {
  43.     int n = s.size();
  44.     if (n % 2 != 0) {
  45.         return 0; // Valid sequence must have even length
  46.     }
  47.  
  48.     // Count valid flips
  49.     int validCount = 0;
  50.     for (int i = 0; i < n; ++i) {
  51.         if (isValidAfterFlip(s, i)) {
  52.             validCount++;
  53.         }
  54.     }
  55.     return validCount;
  56. }
  57.  
  58. int main() {
  59.     ios::sync_with_stdio(false);
  60.     cin.tie(nullptr);
  61.  
  62.     string s;
  63.     cin >> s;
  64.  
  65.     // Validate input
  66.     if (!isValidInput(s)) {
  67.         cout << "Invalid input\n";
  68.         return 1;
  69.     }
  70.  
  71.     // Output the result
  72.     cout << countValidFlips(s) << '\n';
  73.     return 0;
  74. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
()(())))
stdout
copy 
4
https://ideone.com/bFJqBd
language:
C++ (gcc 8.3)
created:
13 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!