Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #pragma comment(linker, "/stack:200000000")
- #pragma GCC optimize("Ofast")
- #pragma GCC optimize("unroll-loops")
- #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
- #include <set>
- #include <map>
- #include <deque>
- #include <cmath>
- #include <queue>
- #include <random>
- #include <bitset>
- #include <time.h>
- #include <string>
- #include <chrono>
- #include <cstdio>
- #include <vector>
- #include <cstdlib>
- #include <iomanip>
- #include <cassert>
- #include <iostream>
- #include <algorithm>
- #include <unordered_map>
- #include <unordered_set>
- //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
- #define itn int
- //#define endl '\n'
- #define mp make_pair
- #define pbc push_back
- #define pob pop_back()
- #define empb emplace_back
- #define sp system("pause")
- #define queuel queue<long long>
- #define matrix vector<vector<ll>>
- #define all(x) (x).begin(),(x).end()
- #define rall(x) (x).rbegin(),(x).rend()
- #define pin(p) cin >> p.first >> p.second;
- #define rev(v) reverse(v.begin(),v.end());
- #define mx(v) max_element(v.begin(), v.end());
- #define mn(v) min_element(v.begin(), v.end());
- #define dig(c) (c >=' 0' && c <= '9') ? 1 : 0
- #define sout(s, c) for(auto i : s) cout << i << c;
- #define pout(p) cout << p.first << " " << p.second;
- #define er(v, l, r) erase(v.begin() + l, v.begin() + r);
- #define vin(v) for(ll i = 0; i < v.size(); ++i) cin >> v[i];
- #define vout(v, c) for(int i = 0; i < v.size(); ++i) cout << v[i] << c;
- #define pushi(v, a) for(int i = 0; i < a.size(); ++i) v.push_back(a[i]);
- #define sin(s, n) for(int i = 0; i < n; ++i){int a; cin >> a; s.insert(a);}
- #define fastio() ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
- //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
- using namespace std;
- /*▄███████▀▀▀▀▀▀███████▄
- ░▐████▀▒ЗАПУСКАЕМ▒▀██████▄
- ░███▀▒▒▒▒▒ДЯДЮ▒▒▒▒▒▒▀█████
- ░▐██▒▒▒▒▒БОГДАНА▒▒▒▒▒████▌
- ░▐█▌▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒████▌
- ░░█▒▄▀▀▀▀▀▄▒▒▄▀▀▀▀▀▄▒▐███▌
- ░░░▐░░░▄▄░░▌▐░░░▄▄░░▌▐███▌
- ░▄▀▌░░░▀▀░░▌▐░░░▀▀░░▌▒▀▒█▌
- ░▌▒▀▄░░░░▄▀▒▒▀▄░░░▄▀▒▒▄▀▒▌
- ░▀▄▐▒▀▀▀▀▒▒▒▒▒▒▀▀▀▒▒▒▒▒▒█
- ░░░▀▌▒▄██▄▄▄▄████▄▒▒▒▒█▀
- ░░░░▄██████████████▒▒▐▌
- ░░░▀███▀▀████▀█████▀▒▌
- ░░░░░▌▒▒▒▄▒▒▒▄▒▒▒▒▒▒▐
- ░░░░░▌▒▒▒▒▀▀▀▒▒▒▒▒▒▒▐*/
- //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
- typedef long long ll;
- typedef long double ld;
- typedef unsigned long long ull;
- //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
- const ll INF = 1000LL * 1000 * 1000 * 1000 * 1000 * 1000;
- const ll inf = 1000 * 1000 * 1000;
- const ld PI = acos(-1.0);
- const ll mod1 = inf * inf + 1337 * 42 + 57 * 179 + 228;
- const ll mod2 = inf + 7;
- const ll bigmod = 1LL * inf * 100 + 3;
- const int MAXN = 300005;
- const ld EPS = 1e-10;
- const int N = 300228;
- ll hp = 1e6 + 3;
- ll ans = 0;
- short dp[701][701][701];
- char p[701][701][701];
- signed main()
- {
- fastio();
- string s1, s2;
- cin >> s1 >> s2;
- s1 = "#" + s1;
- s2 = "#" + s2;
- for (int i = 1; i < s1.size(); ++i)
- {
- for (int j = 1; j < s2.size(); ++j)
- {
- for (int bal = 0; bal < min(s1.size(), s2.size()); ++bal)
- {
- if (s1[i] == s2[j] && s1[i] == '(')
- {
- if (!bal)
- {
- dp[i][j][0] = 1;
- p[i][j][0] = 1;
- continue;
- }
- dp[i][j][bal] = dp[i - 1][j - 1][bal - 1] + 1;
- p[i][j][bal] = 1;
- }
- else if (s1[i] == s2[j] && s1[i] == ')')
- {
- dp[i][j][bal] = dp[i - 1][j - 1][bal + 1] + 1;
- p[i][j][bal] = 2;
- }
- else
- {
- dp[i][j][bal] = max(dp[i - 1][j][bal], dp[i][j - 1][bal]);
- if (dp[i - 1][j][bal] > dp[i][j - 1][bal])
- {
- p[i][j][bal] = 3;
- }
- else
- {
- p[i][j][bal] = 4;
- }
- }
- }
- }
- }
- int ti = s1.size() - 1;
- int tj = s2.size() - 1;
- int tbal = 0;
- string ans = "";
- while (ti && tj)
- {
- if (p[ti][tj][tbal] == 1)
- {
- ans.pbc(')');
- ti--;
- tj--;
- tbal--;
- continue;
- }
- if (p[ti][tj][tbal] == 2)
- {
- ans.pbc('(');
- ti--;
- tj--;
- tbal++;
- continue;
- }
- if (p[ti][tj][tbal] == 3)
- {
- ti--;
- continue;
- }
- else tj--;
- }
- if (!ans.size())return 0;
- while (ans.size() && ans.back() == '(')ans.pob;
- int c1 = count(all(ans), '(');
- int c2 = count(all(ans), ')');
- rev(ans);
- while (c1 > c2 && ans.back() == '(') {
- ans.pob;
- c1--;
- }
- rev(ans);
- while (c2 > c1 && ans.back() == ')') {
- ans.pob;
- c2--;
- }
- rev(ans);for (int i = 0; i < ans.size(); ++i)
- {
- if (ans[i] == '(') ans[i] = ')';
- else ans[i] = '(';
- }
- cout << ans;
- // sp;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement