Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- #define TASK "lcs"
- #define MAXN 50050
- int n, a[2 * MAXN], b[2 * MAXN], c[MAXN][2], f[2 * MAXN], q[2 * MAXN];
- vector<pair<int, int> > p[2 * MAXN];
- int get_max(int x)
- {
- int res = 0;
- for ( ; x >= 0; x &= x + 1, x--)
- res = max(res, f[x]);
- return res;
- }
- void upgrade(int x, int p)
- {
- for ( ; x < n; x |= x + 1)
- f[x] = max(f[x], p);
- }
- void upgrade(int x)
- {
- int val = get_max(x - 1);
- if (val + 1 > f[x])
- {
- int l = -1, r = x - 1, m = (l + r) >> 1;
- while (r - l > 1)
- {
- if (get_max(m) == val)
- r = m;
- else
- l = m;
- m = (l + r) >> 1;
- }
- if (val > 0)
- p[x].push_back(make_pair(r, (int)p[r].size() - 1));
- upgrade(x, val + 1);
- q[x] = val + 1;
- }
- }
- int main()
- {
- ifstream cin(TASK".in");
- ofstream cout(TASK".out");
- while (true)
- {
- cin >> n;
- n <<= 1;
- if (!n)
- break;
- for (int i = 0; i < n; ++i)
- {
- cin >> a[i];
- c[a[i]][0] = c[a[i]][1] = -1;
- }
- for (int i = 0; i < n; ++i)
- {
- cin >> b[i];
- if (c[b[i]][1] == -1)
- c[b[i]][1] = i;
- else
- c[b[i]][0] = i;
- f[i] = q[i] = 0;
- p[i].clear();
- }
- for (int i = 0; i < n; ++i)
- {
- upgrade(c[a[i]][0]);
- upgrade(c[a[i]][1]);
- }
- int ans = get_max(n - 1);
- cout << ans << endl;
- vector<int> ansp;
- pair<int, int> cur;
- for (int i = n - 1; ; --i)
- if (q[i] == ans)
- {
- ansp.push_back(b[i]);
- cur = p[i][p[i].size() - 1];
- break;
- }
- for (int k = ans; ; cur = p[cur.first][cur.second])
- {
- ansp.push_back(b[cur.first]);
- if (cur.second == -1 || p[cur.first].size() == 0)
- break;
- }
- for (vector<int>::reverse_iterator it = ansp.rbegin(); it != ansp.rend(); ++it)
- cout << *it << " ";
- cout << endl;
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment