Cod sursa(job #372629)

Utilizator pregatireCont de pregatire pregatire Data 10 decembrie 2009 23:24:50
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.63 kb
#include <stdio.h>

int M, N, sol[1024], bst;
int A[1024], B[1024], opt[2][1024], tai[2][1024];

inline int get_opt(int l1, int l2, int l, int c, int idx)
{
    if (l < l1 || c < l2)
        return 0;
    return opt[idx][c];
}

inline int get_tai(int l1, int l2, int l, int c, int idx)
{
    if (l < l1 || c < l2)
        return l2-1;
    return tai[idx][c];
}

void solve(int l1, int r1, int l2, int r2)
{
    if (l1 > r1 || l2 > r2)
        return ;

    //printf("...... %d %d %d %d\n", l1, r1, l2, r2);    
    
    int i, j;
    if (l1 == r1 || l2 == r2)
    {
        for (i = l1; i <= r1; ++i)
            for (j = l2; j <= r2; ++j)
                if (A[i] == B[j])
                {
                    sol[i] = 1;
                    ++bst;
                    return ;
                }
        return ;
    }
    
    int m = (l1 + r1) / 2;
    int crt = 1, prev = 0;

    for (i = l1; i <= r1; ++i)
    {
        crt ^= 1; prev ^= 1;
        
        for (j = l2; j <= r2; ++j)
            if (A[i] == B[j])
            {
                opt[crt][j] = get_opt(l1, l2, i-1, j-1, prev) + 1;                    
                tai[crt][j] = get_tai(l1, l2, i-1, j-1, prev);
                if (i <= m)
                    tai[crt][j] = j;
            }
            else
            {
                int i1 = get_opt(l1, l2, i, j-1, crt);
                int i2 = get_opt(l1, l2, i-1, j, prev);
                if (i1 > i2)
                {
                    opt[crt][j] = i1;
                    tai[crt][j] = get_tai(l1, l2, i, j-1, crt);
                }
                else
                {
                    opt[crt][j] = i2;
                    tai[crt][j] = get_tai(l1, l2, i-1, j, prev);                
                }
            }
    }
    
    //if (l1 == 1 && l2 == 1 && r1 == M && r2 == N)
    //    printf("? %d %d\n", opt[crt][r2], tai[crt][r2]);
        
    //printf("...... %d %d %d %d -> optim %d, tai la %d\n", l1, r1, l2, r2, opt[crt][r2], tai[crt][r2]);
    
    int x = tai[crt][r2];
//    if (x == 0)
//        return ;
    solve(l1, m, l2, x);
    solve(m+1, r1, x+1, r2);
}

int main()
{
    int i, j;
    
    freopen("cmlsc.in", "r", stdin);
    freopen("cmlsc.out", "w", stdout);
    
    scanf("%d %d", &M, &N);
    for (i = 1; i <= M; ++i)
        scanf("%d", &A[i]);
    for (j = 1; j <= N; ++j)
        scanf("%d", &B[j]);
    
    solve(1, M, 1, N);    
    
    printf("%d\n", bst);
    for (i = 1; i <= M; ++i)
        if (sol[i])
            printf("%d ", A[i]);
    printf("\n");

   // for (;;);
    
    return 0;
}