Cod sursa(job #2254982)

Utilizator Kln1000Ciobanu Bogdan Kln1000 Data 6 octombrie 2018 11:59:17
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.21 kb
#include <bits/stdc++.h>

using namespace std;

class parser{
    public:
        parser() {}
        parser(const char *file_name){
            input_file.open(file_name,ios::in | ios::binary);
            input_file.sync_with_stdio(false);
            index&=0;
            input_file.read(buffer,SIZE);}
        inline parser &operator >>(int &n){
            for (;buffer[index]<'0' or buffer[index]>'9';inc());
            n&=0;
            //sign&=0;
            //sign|=(buffer[index-1]=='-');
            for (;'0'<=buffer[index] and buffer[index]<='9';inc())
                n=(n<<1)+(n<<3)+buffer[index]-'0';
            //n^=((n^-n)&-sign);
            return *this;}
        ~parser(){
            input_file.close();}
    private:
        fstream input_file;
        static const int SIZE=0x20000; ///0.2MB
        char buffer[SIZE];
        int index/*,sign*/;
        inline void inc(){
            if(++index==SIZE)
                index=0,input_file.read(buffer,SIZE);}
};

class writer{
    public:
        writer() {};
        writer(const char *file_name){
            output_file.open(file_name,ios::out | ios::binary);
            output_file.sync_with_stdio(false);
            index&=0;}
        inline writer &operator <<(int target){
            aux&=0;
            //sign&=0;
            n=target;
            /*if (n<0)
                sign=1,
                buffer[index]='-',
                inc();
            n^=((n^-n)&-sign);*/
            if (!n)
                nr[aux++]='0';
            for (;n;n/=10)
                nr[aux++]=n%10+'0';
            for(;aux;inc())
                buffer[index]=nr[--aux];
            return *this;}
        inline writer &operator <<(const char *target){
            aux&=0;
            while (target[aux])
                buffer[index]=target[aux++],inc();
            return *this;}
        ~writer(){
            output_file.write(buffer,index);output_file.close();}
    private:
        fstream output_file;
        static const int SIZE=0x10000; ///0.1MB
        int index,aux,n/*,sign*/;
        char buffer[SIZE],nr[24];
        inline void inc(){
            if(++index==SIZE)
                index&=0,output_file.write(buffer,SIZE);}
};

parser f ("cmlsc.in");
writer t ("cmlsc.out");

int m,n;
vector <int> v1,v2,sol;

int max(const int x,const int y,const int z){
if (x>=y and x>=z) return x;
if (y>=x and y>=z) return y;
if (z>=x and z>=y) return z;
return -1;}

void read(){
f>>m>>n;
v1.resize(m);
v2.resize(n);
for (int i=0;i<m;++i)
f>>v1[i];
for (int i=0;i<n;++i)
f>>v2[i];
}

void solve(){
int d[m+1][n+1];
memset(d,0,sizeof(d));
for (int i=1;i<=m;++i)
for (int j=1;j<=n;++j)
d[i][j]=max(d[i-1][j-1]+(v1[i-1]==v2[j-1]),d[i-1][j],d[i][j-1]);
t<<d[m][n]<<"\n";
int i=m,j=n;
get_heritage:
    if(d[i][j] == 0) goto fin;
    if(v1[i-1]==v2[j-1])
    {
        sol.push_back(v1[i-1]);
        --i,--j;
        goto get_heritage;
    }
    else if(d[i][j] == d[i-1][j]){
        --i;
        goto get_heritage;}
    else{
        --j;
        goto get_heritage;}
   fin:for (int i=d[m][n]-1;i>=0;--i)
   t<<sol[i]<<" ";
}

int main()
{
    read();
    solve();
    return 0;
}