fork download
copy 
  1. //#pragma GCC optimize("O3", "unroll-loops")
  2. //#pragma GCC target("avx2", "bmi", "bmi2", "lzcnt", "popcnt")
  3.  
  4. #include <bits/stdc++.h>
  5. #define ldb long double
  6. //#define double ldb
  7. #define db double
  8. #define unomap unordered_map
  9. #define unoset unordered_set
  10. #define endl '\n'
  11. #define str string
  12. #define strstr stringstream
  13. #define sz(a) (int)a.size()
  14. #define ll long long
  15. //#define int ll
  16. #define pii pair <int, int>
  17. #define pll pair <ll, ll>
  18. #define Unique(a) a.resize(unique(all(a)) - a.begin())
  19. #define ull unsigned ll
  20. #define fir first
  21. #define sec second
  22. #define idc cin.ignore()
  23. #define lb lower_bound
  24. #define ub upper_bound
  25. #define all(s) s.begin(), s.end()
  26. #define rev reverse
  27. #define sigma ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  28. #define skibidi int main
  29. #define rizz signed main
  30. #define gcd __gcd
  31. #define pushb push_back
  32. #define popb pop_back
  33. #define pushf push_front
  34. #define popf pop_front
  35. #define mul2x(a, x) a << x
  36. #define div2x(a, x) a >> x
  37. #define lcm(a, b) (a / __gcd(a, b) * b)
  38. #define log_base(x, base) log(x) / log(base)
  39. #define debug clog << "No errors!"; exit(0);
  40. #define forw(i, a, b) for (int i = a; i <= b; ++i)
  41. #define forw2(i, a, b) for (ll i = a; i <= b; ++i)
  42. #define fors(i, a, b) for (int i = a; i >= b; --i)
  43. #define fors2(i, a, b) for (ll i = a; i >= b; --i)
  44. #define pqueue priority_queue
  45. #define sqrt sqrtl
  46. #define popcount __builtin_popcountll
  47. #define want_digit(x) cout << fixed << setprecision(x);
  48. #define excuting_time 1000.0 * clock() / CLOCKS_PER_SEC
  49. using namespace std;
  50. const int MOD = 1e9 + 7; // 998244353
  51. const int inf = 1e9;
  52. const ll INF = 1e18;
  53. const int N = 100;
  54.  
  55. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  56. ll random(const ll &L, const ll &R)
  57. {
  58.     return uniform_int_distribution<ll> (L, R) (rng);
  59. }
  60.  
  61. str add(str a, str b)
  62. {
  63.     str c;
  64.     int re = 0, digit;
  65.     rev(all(a));
  66.     rev(all(b));
  67.     while (sz(a) < sz(b)) a += '0';
  68.     while (sz(b) < sz(a)) b += '0';
  69.  
  70.     forw (i, 0, sz(a) - 1)
  71.     {
  72.         digit = (a[i] - '0') + (b[i] - '0') + re;
  73.         re = digit / 10;
  74.         digit %= 10;
  75.         c += char(digit + '0');
  76.     }
  77.     if (re) c += '1';
  78.  
  79.     rev(all(c));
  80.     return c;
  81. }
  82.  
  83. str sub(str a, str b)
  84. {
  85.     str c;
  86.     int re = 0, digit;
  87.     rev(all(a)); rev(all(b));
  88.     while (sz(b) < sz(a)) b += '0';
  89.     forw (i, 0, sz(a) - 1)
  90.     {
  91.         digit = (a[i] - '0') - (b[i] - '0') - re;
  92.         re = (digit < 0);
  93.         digit = (digit + 10) % 10;
  94.         c += char(digit + '0');
  95.     }
  96.  
  97.     while (sz(c) > 1 && c.back() == '0') c.popb();
  98.     rev(all(c));
  99.     return c;
  100. }
  101.  
  102. bool compare(str a, str b)
  103. {
  104.     if (sz(a) > sz(b)) return true;
  105.     if (sz(a) < sz(b)) return false;
  106.     return (a >= b);
  107. }
  108.  
  109. int n, k;
  110. str s, res, dp[N + 5][N / 2 + 5][N / 2 + 5], curr, ans, t;
  111.  
  112. str f(int pos, int open, int depth)
  113. {
  114.     if (open < 0 || open > n - pos || depth > k) return "0";
  115.     if (pos == n) return (!open && depth == k) ? "1" : "0";
  116.  
  117.     str &X = dp[pos][open][depth];
  118.     if (X != "-1") return X;
  119.  
  120.     X = add(f(pos + 1, open + 1, max(depth, open + 1)), f(pos + 1, open - 1, depth));
  121.     return X;
  122. }
  123.  
  124. void cook()
  125. {
  126.     cin >> n >> k >> s >> t;
  127.     forw (i, 1, n) forw (j, 0, n / 2) forw (p, 0, n / 2)
  128.         dp[i][j][p] = "-1";
  129.  
  130.     int open = 0, depth = 0;
  131.     forw (pos, 0, n - 1)
  132.     {
  133.         if (s[pos] == '(')
  134.             depth = max(depth, ++open);
  135.         else
  136.         {
  137.             ans = add(ans, f(pos + 1, open + 1, max(depth, open + 1)));
  138.             --open;
  139.         }
  140.     }
  141.     cout << add(ans, "1") << endl;
  142.  
  143.     open = 0; depth = 0;
  144.     forw (pos, 0, n - 1)
  145.     {
  146.         curr = f(pos + 1, open + 1, max(depth, open + 1));
  147.         if (compare(curr, t))
  148.         {
  149.             res += '(';
  150.             depth = max(depth, ++open);
  151.         }
  152.         else
  153.         {
  154.             t = sub(t, curr);
  155.             res += ')';
  156.             --open;
  157.         }
  158.  
  159.         if (open < 0)
  160.         {
  161.             cout << "-1\n";
  162.             return;
  163.         }
  164.     }
  165.     cout << res << endl;
  166. }
  167.  
  168. skibidi()
  169. //rizz()
  170. {
  171.     srand(time(NULL));
  172.     sigma;
  173.     #define name "test"
  174.     /*
  175.     if (fopen(name".INP", "r"))
  176.     {
  177.         freopen(name".INP", "r", stdin);
  178.         freopen(name".OUT", "w", stdout);
  179.     }
  180.     */
  181.     int numTest = 1;
  182. //    cin >> numTest;
  183.     while (numTest--)
  184.     {
  185.         cook();
  186.     }
  187.     return 0;
  188. }
  189.  
Success #stdin #stdout 0.01s 13552KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/Duucc1
language:
C++14 (gcc 8.3)
created:
4 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!