Advertisement
Guest User

Untitled

a guest
Dec 14th, 2018
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.63 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #pragma comment(linker, "/stack:200000000")
  3. #pragma GCC optimize("Ofast")
  4. #pragma GCC optimize("unroll-loops")
  5. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  6.  
  7. #include <set>
  8. #include <map>
  9. #include <deque>
  10. #include <cmath>
  11. #include <queue>
  12. #include <random>
  13. #include <bitset>
  14. #include <time.h>
  15. #include <string>
  16. #include <chrono>
  17. #include <cstdio>
  18. #include <vector>
  19. #include <cstdlib>
  20. #include <iomanip>
  21. #include <cassert>
  22. #include <iostream>
  23. #include <algorithm>
  24. #include <unordered_map>
  25. #include <unordered_set>
  26. //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
  27. #define itn int
  28. //#define endl '\n'
  29. #define mp make_pair
  30. #define pbc push_back
  31. #define pob pop_back()
  32. #define empb emplace_back
  33. #define sp system("pause")
  34. #define queuel queue<long long>
  35. #define matrix vector<vector<ll>>
  36. #define all(x) (x).begin(),(x).end()
  37. #define rall(x) (x).rbegin(),(x).rend()
  38. #define pin(p) cin >> p.first >> p.second;
  39. #define rev(v) reverse(v.begin(),v.end());
  40. #define mx(v) max_element(v.begin(), v.end());
  41. #define mn(v) min_element(v.begin(), v.end());
  42. #define dig(c) (c >=' 0' && c <= '9') ? 1 : 0
  43. #define sout(s, c) for(auto i : s) cout << i << c;
  44. #define pout(p) cout << p.first << " " << p.second;
  45. #define er(v, l, r) erase(v.begin() + l, v.begin() + r);
  46. #define vin(v) for(ll i = 0; i < v.size(); ++i) cin >> v[i];
  47. #define vout(v, c) for(int i = 0; i < v.size(); ++i) cout << v[i] << c;
  48. #define pushi(v, a) for(int i = 0; i < a.size(); ++i) v.push_back(a[i]);
  49. #define sin(s, n) for(int i = 0; i < n; ++i){int a; cin >> a; s.insert(a);}
  50. #define fastio() ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
  51. //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
  52. using namespace std;
  53. /*▄███████▀▀▀▀▀▀███████▄
  54. ░▐████▀▒ЗАПУСКАЕМ▒▀██████▄
  55. ░███▀▒▒▒▒▒ДЯДЮ▒▒▒▒▒▒▀█████
  56. ░▐██▒▒▒▒▒БОГДАНА▒▒▒▒▒████▌
  57. ░▐█▌▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒████▌
  58. ░░█▒▄▀▀▀▀▀▄▒▒▄▀▀▀▀▀▄▒▐███▌
  59. ░░░▐░░░▄▄░░▌▐░░░▄▄░░▌▐███▌
  60. ░▄▀▌░░░▀▀░░▌▐░░░▀▀░░▌▒▀▒█▌
  61. ░▌▒▀▄░░░░▄▀▒▒▀▄░░░▄▀▒▒▄▀▒▌
  62. ░▀▄▐▒▀▀▀▀▒▒▒▒▒▒▀▀▀▒▒▒▒▒▒█
  63. ░░░▀▌▒▄██▄▄▄▄████▄▒▒▒▒█▀
  64. ░░░░▄██████████████▒▒▐▌
  65. ░░░▀███▀▀████▀█████▀▒▌
  66. ░░░░░▌▒▒▒▄▒▒▒▄▒▒▒▒▒▒▐
  67. ░░░░░▌▒▒▒▒▀▀▀▒▒▒▒▒▒▒▐*/
  68. //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
  69. typedef long long ll;
  70. typedef long double ld;
  71. typedef unsigned long long ull;
  72. //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
  73. const ll INF = 1000LL * 1000 * 1000 * 1000 * 1000 * 1000;
  74. const ll inf = 1000 * 1000 * 1000;
  75. const ld PI = acos(-1.0);
  76. const ll mod1 = inf * inf + 1337 * 42 + 57 * 179 + 228;
  77. const ll mod2 = inf + 7;
  78. const ll bigmod = 1LL * inf * 100 + 3;
  79. const int MAXN = 300005;
  80. const ld EPS = 1e-10;
  81. const int N = 300228;
  82. ll hp = 1e6 + 3;
  83. ll ans = 0;
  84. short dp[701][701][701];
  85. char p[701][701][701];
  86. signed main()
  87. {
  88. fastio();
  89. string s1, s2;
  90. cin >> s1 >> s2;
  91. s1 = "#" + s1;
  92. s2 = "#" + s2;
  93. for (int i = 1; i < s1.size(); ++i)
  94. {
  95. for (int j = 1; j < s2.size(); ++j)
  96. {
  97. for (int bal = 0; bal < min(s1.size(), s2.size()); ++bal)
  98. {
  99. if (s1[i] == s2[j] && s1[i] == '(')
  100. {
  101. if (!bal)
  102. {
  103. dp[i][j][0] = 1;
  104. p[i][j][0] = 1;
  105. continue;
  106. }
  107. dp[i][j][bal] = dp[i - 1][j - 1][bal - 1] + 1;
  108. p[i][j][bal] = 1;
  109. }
  110. else if (s1[i] == s2[j] && s1[i] == ')')
  111. {
  112. dp[i][j][bal] = dp[i - 1][j - 1][bal + 1] + 1;
  113. p[i][j][bal] = 2;
  114. }
  115. else
  116. {
  117. dp[i][j][bal] = max(dp[i - 1][j][bal], dp[i][j - 1][bal]);
  118. if (dp[i - 1][j][bal] > dp[i][j - 1][bal])
  119. {
  120. p[i][j][bal] = 3;
  121. }
  122. else
  123. {
  124. p[i][j][bal] = 4;
  125. }
  126. }
  127. }
  128. }
  129. }
  130. int ti = s1.size() - 1;
  131. int tj = s2.size() - 1;
  132. int tbal = 0;
  133. string ans = "";
  134. while (ti && tj)
  135. {
  136. if (p[ti][tj][tbal] == 1)
  137. {
  138. ans.pbc(')');
  139. ti--;
  140. tj--;
  141. tbal--;
  142. continue;
  143. }
  144. if (p[ti][tj][tbal] == 2)
  145. {
  146. ans.pbc('(');
  147. ti--;
  148. tj--;
  149. tbal++;
  150. continue;
  151. }
  152. if (p[ti][tj][tbal] == 3)
  153. {
  154. ti--;
  155. continue;
  156. }
  157. else tj--;
  158. }
  159. if (!ans.size())return 0;
  160.  
  161.  
  162. while (ans.size() && ans.back() == '(')ans.pob;
  163. int c1 = count(all(ans), '(');
  164. int c2 = count(all(ans), ')');
  165. rev(ans);
  166. while (c1 > c2 && ans.back() == '(') {
  167. ans.pob;
  168. c1--;
  169. }
  170. rev(ans);
  171. while (c2 > c1 && ans.back() == ')') {
  172. ans.pob;
  173. c2--;
  174. }
  175. rev(ans);for (int i = 0; i < ans.size(); ++i)
  176. {
  177. if (ans[i] == '(') ans[i] = ')';
  178. else ans[i] = '(';
  179. }
  180. cout << ans;
  181. // sp;
  182. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement