SHARE
TWEET

Untitled

a guest Dec 14th, 2018 58 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top