fork download 
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4. #pragma GCC diagnostic ignored "-Wlong-long"
  5. using namespace std;
  6. int n;
  7. char s[500001];
  8. int lval[500000];
  9. int rval[500000];
  10.  
  11. bool is_possible() {
  12.     int l = 0, r = 0; // [l, r]
  13.     for(int i = 0; i < n; i++) {
  14.         switch(s[i]) {
  15.         case '(': l++; r++; break;
  16.         case ')': l--; r--; break;
  17.         case '?': l--; r++; break;
  18.         }
  19.         if(l < 0) l += 2;
  20.         if(l > r) return false;
  21.     }
  22.     return l == 0;
  23. }
  24.  
  25. struct Cmp {
  26.     bool operator() (int lhs, int rhs) {
  27.          return (long long) rval[lhs] - lval[lhs] < (long long) rval[rhs] - lval[rhs];
  28.     }
  29. };
  30.  
  31. int vec[500000];
  32.  
  33. long long solve() {
  34.     int m = 0;
  35.     for(int i = 0; i < n; i++)
  36.         if(s[i] == '?')
  37.             vec[m++] = i;
  38.     sort(vec, vec + m, Cmp());
  39.     long long val = 0;
  40.     for(int index = 0; index < m; index++) {
  41.         int i = vec[index];
  42.         s[i] = ')';
  43.         if(is_possible()) {
  44.             val += rval[i];
  45.         } else {
  46.             s[i] = '(';
  47.             val += lval[i];
  48.         }
  49.     }
  50.     return val;
  51. }
  52.  
  53. int main(){
  54.     int t;
  55.     scanf("%d", &t);
  56.     while(t--) {
  57.         scanf("%s", s);
  58.         n = strlen(s);
  59.         for(int i = 0; i < n; i++)
  60.             if(s[i] == '?')
  61.                 scanf("%d %d", lval + i, rval + i);
  62.         if(is_possible()) {
  63.             #pragma GCC diagnostic push
  64.             #pragma GCC diagnostic ignored "-Wformat"
  65.             printf("%lld\n", solve());
  66.             #pragma GCC diagnostic pop
  67.         } else {
  68.             puts("IMBA");
  69.         }
  70.     }
  71. }
  72.  
Success #stdin #stdout 0s 9696KB
comments (?)
stdin 
4
(())
(??)
1 10
10 100
?????)))))
2 1
2 1
2 1
2 1
2 1
(((((?
2147483647 -2147483648
stdout 
0
20
10
IMBA
https://ideone.com/s5Cj0L
language:
C++ (gcc 8.3)
created:
10 years 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!