fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define FILENAME "LCKSTR"
  4. #define ll long long 
  5. #define el cout << '\n'
  6. #define ii pair<ll, ll>
  7. #define fi first 
  8. #define se second 
  9. #define pb push_back
  10. #define YES cout << "YES", el
  11. #define NO cout << "NO", el
  12. #define print_type cout
  13. #define print_el print_type << '\n'
  14. #define DEBUG(...) [](auto && ... x) {int i = 0; ((print_type << (i++ ? " " : "") << x), ...), print_el;} (__VA_ARGS__)
  15. #define bit(mask, i) (((mask) >> (i)) & 1)
  16. #define BIT(n) (1ll << (n))
  17.  
  18. using namespace std;
  19.  
  20. const bool is_brute = 0;
  21. const bool multi_test = 0;
  22.  
  23. const int maxn = 180;
  24. const int maxm = 227;
  25. const int maxk = 26;
  26. const int INF = 1e9;
  27.  
  28. struct Parents
  29. {
  30.     int x, y;
  31.     char c;
  32.  
  33.     Parents() {};
  34.     Parents(int x, int y, char c) :
  35.         x(x), y(y), c(c) {};
  36. };
  37. struct Child
  38. {
  39.     int k;
  40.     char x, y;
  41.  
  42.     Child() {};
  43.     Child(int k, char x, char y) :
  44.         k(k), x(x), y(y) {};
  45.     friend ostream & operator << (ostream &cout, Child p)
  46.     {
  47.         cout << p.k << ' ' << p.x << ' ' << p.y;
  48.         return cout;
  49.     }
  50. };
  51.  
  52. int n, m, q, dp[maxn + 10][maxn + 10], dpa[maxn + 10][maxn + 10], dpb[maxn + 10][maxn + 10];
  53. Child ca[maxn + 10][maxn + 10][maxk + 10], cb[maxn + 10][maxn + 10][maxk + 10]; 
  54. string a, b, c[maxm + 10];
  55. Parents par[maxn + 10][maxn + 10];
  56. vector<string> ansa, ansb;
  57.  
  58. void DP(int n, string a, int dp[maxn + 10][maxn + 10], Child p[maxn + 10][maxn + 10][maxk + 10])
  59. {
  60.     for (int i = 1; i <= n; i++)
  61.         dp[i][i] |= BIT(a[i] - 'a');
  62.     for (int l = n; l >= 1; l--)
  63.         for (int r = l + 1; r <= n; r++)
  64.         {
  65.             for (int t = 1; t <= q; t++)
  66.             {
  67.                 int x = c[t][0] - 'a';
  68.                 int y = c[t][1] - 'a';
  69.                 int z = c[t][2] - 'a';
  70.                 if (bit(dp[l][r], x))
  71.                     continue;
  72.                 for (int k = l; k <= r - 1; k++)
  73.                     if (bit(dp[l][k], y) && bit(dp[k + 1][r], z))
  74.                     {
  75.                         p[l][r][x] = Child(k, y + 'a', z + 'a');
  76.                         dp[l][r] |= BIT(x);
  77.                         break;
  78.                     }
  79.             }
  80.         }
  81. }
  82. void TRACE(int l, int r, char e, Child ch[maxn + 10][maxn + 10][maxk + 10], int n, string &a, vector<string> &ans)
  83. {
  84.     if (l == r)
  85.         return ;
  86.     Child t = ch[l][r][e - 'a'];
  87.     TRACE(l, t.k, t.x, ch, n, a, ans);
  88.     TRACE(t.k + 1, r, t.y, ch, n, a, ans);
  89.     auto getString = [=] (string a)
  90.     {
  91.         string ans = "";
  92.         for (int i = 1; i <= n; i++)
  93.             if (a[i] != '#')
  94.                 ans += a[i];
  95.         return ans;
  96.     };
  97.     for (int i = l; i <= r; i++)
  98.         a[i] = '#';
  99.     a[l] = e;
  100.     ans.push_back(getString(a));
  101. }
  102.  
  103. void solve()
  104. {
  105.     cin >> a;
  106.     cin >> b;
  107.     cin >> q;
  108.     for (int i = 1; i <= q; i++)
  109.         cin >> c[i];
  110.     n = a.size();
  111.     m = b.size();
  112.     a = ' ' + a;
  113.     b = ' ' + b;
  114.     DP(n, a, dpa, ca);
  115.     DP(m, b, dpb, cb);
  116.     for (int i = 0; i <= n; i++)
  117.         for (int j = 0; j <= m; j++)
  118.             dp[i][j] = INF;
  119.     dp[0][0] = 0;
  120.     for (int i = 1; i <= n; i++)
  121.         for (int j = 1; j <= m; j++)
  122.         {
  123.             for (int x = i; x >= 1; x--)
  124.             {
  125.                 if (dpa[x][i] == 0)
  126.                     continue;
  127.                 for (int y = j; y >= 1; y--)
  128.                 {
  129.                     if ((dpa[x][i] & dpb[y][j]) == 0)
  130.                         continue;
  131.                     if (dp[i][j] > dp[x - 1][y - 1] + i - x + j - y)
  132.                     {
  133.                         int c = __builtin_ctz(dpa[x][i] & dpb[y][j]) + 'a';
  134.                         dp[i][j] = dp[x - 1][y - 1] + i - x + j - y;
  135.                         par[i][j] = Parents(x - 1, y - 1, c);
  136.                     }
  137.                 }
  138.             }
  139.         }
  140.     cout << dp[n][m] << ' ';
  141.     int tn = n, tm = m;
  142.     string ans = "";
  143.     ansa.push_back(a);
  144.     ansb.push_back(b);
  145.     while (tn && tm)
  146.     {
  147.         Parents pr = par[tn][tm];
  148.         ans.push_back(pr.c);
  149.         TRACE(pr.x + 1, tn, pr.c, ca, n, a, ansa);
  150.         TRACE(pr.y + 1, tm, pr.c, cb, m, b, ansb);
  151.         tn = pr.x;
  152.         tm = pr.y;
  153.     }
  154.     ansa.pop_back();
  155.     ansb.pop_back();
  156.     reverse(ans.begin(), ans.end());
  157.     reverse(ansa.begin(), ansa.end());
  158.     reverse(ansb.begin(), ansb.end());
  159.     cout << ans, el;
  160.     cout << ansa.size();
  161.     for (string resa : ansa)
  162.     {
  163.         if (resa != ansa.back())
  164.             cout << ' ';
  165.         cout << resa;
  166.     }
  167.     el;
  168.     cout << ansb.size();
  169.     for (string resb : ansb)
  170.     {
  171.         if (resb != ansb.back())
  172.             cout << ' ';
  173.         cout << resb;
  174.     }
  175. }
  176.  
  177. int main()
  178. {
  179.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  180.     if (fopen(FILENAME".INP", "r"))
  181.     {
  182.         freopen(FILENAME".INP", "r", stdin);
  183.         if (is_brute)
  184.             freopen(FILENAME"_TRAU.OUT", "w", stdout);
  185.         else
  186.             freopen(FILENAME".OUT", "w", stdout);
  187.     }
  188.  
  189.     int ntest;
  190.     if (multi_test)
  191.         cin >> ntest;
  192.     else
  193.         ntest = 1;
  194.     for (int itest = 1; itest <= ntest; itest++)
  195.     {
  196.         // cout << itest, el;
  197.         solve();
  198.     }
  199. }
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 
0
0
https://ideone.com/ZcLpD8
language:
C++14 (gcc 8.3)
created:
14 hours 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!