Cod sursa(job #2421430)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 15 mai 2019 08:20:39
Problema Cel mai lung subsir comun Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include<cstdio>
#include<vector>
using namespace std;
#define SIGMA 512
#define MAXP 2048
#define pb push_back
#define mkp make_pair
int X[MAXP], Y[MAXP],N, M, P, S[MAXP];
vector <int> alpha[SIGMA];
vector <pair<int, int> > A[MAXP];
void recon(int l, int c, int layer)
{
	if (layer <= 0)
        printf("%d ", X[l]);
	for (int i = 0; i < A[layer].size(); ++i)
	{
		int nl = A[layer][i].first;
		int nc = A[layer][i].second;
		if (nl < l && nc < c)
        {
			recon(nl, nc, layer - 1);
			break;
        }
	}
}
int main()
{
	freopen ("cmlsc.in", "r", stdin);
	freopen ("cmlsc.out", "w", stdout);
	scanf ("%d %d", &N, &M);
	for (int i = 0; i < N; ++i) scanf ("%d", &X[i]);
	for (int i = 0; i < M; ++i) scanf ("%d", &Y[i]);
	for (int i = 0; i < M; ++i) alpha[Y[i]].pb(i);
	for (int i = 0; i < MAXP; ++i) S[i] = M;
	for (int i = 0; i < N; ++i)
	{
		int ind = X[i];
		int curA = 1;
		int curS = S[curA];
		for (int j = 0; j < alpha[ind].size();)
		{
			int pos = alpha[ind][j];
			P = max(P, curA);
			if (pos <= S[curA])
			{
				A[curA].pb(mkp(i,pos));
				curS = min(curS, pos);
				++j;
			}
			else
			{
				S[curA] = curS;
				++curA;
				curS = S[curA];
			}
		}
		S[curA] = curS;
	}
	printf ("%d\n", P);
	int l = A[P][0].first, c= A[P][0].second;
	recon(l, c, P-1);
}