Cod sursa(job #1696444)

Utilizator xtreme77Patrick Sava xtreme77 Data 29 aprilie 2016 02:19:48
Problema ADN Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.12 kb
/**
 * Code by Patrick Sava
 * "Spiru Haret" National College of Bucharest
 **/

# include "fstream"
# include "cstring"
# include "vector"
# include "queue"
# include "bitset"
# include "algorithm"
# include "map"
# include "set"
# include "unordered_map"
# include "deque"
# include "string"
# include "iomanip"
# include "cmath"
# include "stack"
# include "cassert"

const char IN [ ] =  "adn.in" ;
const char OUT [ ] = "adn.out" ;

using namespace std ;

# define pb push_back
# define mp make_pair
# define FORN( a , b , c ) for ( register int a = b ; a <= c ; ++ a )
# define FORNBACK( a , b , c ) for ( register int a = b ; a >= c ; -- a )

ifstream cin ( IN ) ;
ofstream cout ( OUT ) ;

const int MAX = 30014 ;
const int CATE = 20 ;
const unsigned long long B = 71 ;

unsigned long long H [ CATE ] [ MAX ] ;
unsigned long long p [ MAX ] ;
char sir [ CATE ] [ MAX ] ;

int comun [ CATE ] [ CATE ] ;

unsigned long long hash_pe_interval ( int indice , int i , int j )
{
    return H [ indice ] [ i ] - H [ indice ] [ j + 1 ] * p [ j - i + 1 ] ;
}

int len [ CATE ] ;

bitset < CATE > unuseful ;

int indice [ CATE ] ;
int invers [ CATE ] ;

vector < int > gr [ CATE ] ;

int dp [ 1 << CATE ] [ CATE ] ;
int ultimul [ 1 << CATE ] [ CATE ] ;

char sol [ CATE * MAX ] ; int sz ;

int main()
{
    int n ;
    cin >> n ;
    FORN ( i , 1 , n ) {
        cin >> ( sir [ i ] + 1 ) ;
        len [ i ] = strlen ( sir [ i ] + 1 ) ;
    }
    FORN ( j , 1 , n ) {
        int l = len [ j ] ;
        FORNBACK ( i , l , 1 ) {
            H [ j ] [ i ] = H [ j ] [ i + 1 ] * B + sir [ j ] [ i ] ;
        }
    }
    p [ 0 ] = 1 ;
    FORN ( i , 1 , 30000 ) {
        p [ i ] = p [ i - 1 ] * B ;
    }
    FORN ( i , 1 , n ) {
        FORN ( j , 1 , n ) {
            if ( i == j ) {
                continue ;
            }
            if ( len [ i ] > len [ j ] ) {
                continue ;
            }
            int lim = len [ j ] - len [ i ] + 1 ;
            unsigned long long boss = hash_pe_interval ( i , 1 , len [ i ] ) ;
            int ok = 0 ;
            FORN ( k , 1 , lim ) {
                if ( boss == hash_pe_interval ( j , k , k + len [ i ] - 1 ) ) {
                    ok = 1 ;
                    break ;
                }
            }
            if ( ok ) {
                unuseful [ i ] = 1 ;
            }
        }
    }
    int p = -1 ;
    FORN ( i , 1 , n ) {
        if ( unuseful [ i ] ) {
            continue ;
        }
        indice [ i ] = ++ p ;
        invers [ p ] = i ;
    }
    FORN ( i , 1 , n ) {
        FORN ( j , 1 , n ) {
            if ( i == j or unuseful [ i ] or unuseful [ j ] ) {
                continue ;
            }
            int found = 0 ;
            FORN ( k , 1 , len [ i ] )
            {
                if ( hash_pe_interval ( i , k , len [ i ] ) == hash_pe_interval ( j , 1 , len [ i ] - k + 1 ) ) {
                    found = len [ i ] - k + 1 ;
                    break ;
                }
            }
            //cout << " intre " << i << " si " << j << " exista " << found << '\n' ;
            comun [ indice [ i ] ] [ indice [ j ] ] = found ;
            gr [ indice [ i ] ].pb ( indice [ j ] ) ;
        }
    }
    int lim = 1 << ( p + 1 ) ;
    -- lim ;
    FORN ( j , 0 , p ) {
        ultimul [ 1 << j ] [ j ] = -1 ;
    }
    FORN ( i , 0 , lim )
    {
        FORN ( j , 0 , p ) {
            if ( i & ( 1 << j ) ) {
                for ( auto x : gr [ j ] ) {
                    if ( i & ( 1 << x ) ) {
                        continue ;
                    }
                    if ( dp [ i ^ ( 1 << x ) ] [ x ] <= dp [ i ] [ j ] + comun [ j ] [ x ] ) {
                        dp [ i ^ ( 1 << x ) ] [ x ] = dp [ i ] [ j ] + comun [ j ] [ x ] ;
                        ultimul [ i ^ ( 1 << x ) ] [ x ] = j ;
                    }
                }
            }
        }
    }
    int pozitie = 0 ;
    int best = 0 ;
    FORN ( j , 0 , p ) {
        if ( dp [ lim ] [ j ] >= best ) {
            best = dp [ lim ] [ j ] ;
            pozitie = j ;
        }
    }
    int state = lim ;
    int prev = -1 ;
    while ( state and !( pozitie == -1 ) )
    {
        //cout << invers [ pozitie ] << '\n' ;
        if ( state == lim ) {
            FORNBACK ( i , len [ invers [ pozitie ] ] , 1 ) {
                ++ sz ;
                sol [ sz ] = sir [ invers [ pozitie ] ] [ i ] ;
            }
            int urm = ultimul [ state ] [ pozitie ] ;
            state ^= ( 1 << pozitie ) ;
            prev = pozitie ;
            pozitie = urm ;
            continue ;
        }
        int delay = comun [ pozitie ] [ prev ] ;
        int limm = len [ invers [ pozitie ] ] - delay ;
        FORNBACK ( i , limm , 1 ) {
            ++ sz ;
            sol [ sz ] = sir [ invers [ pozitie ] ] [ i ] ;
        }
        int urm = ultimul [ state ] [ pozitie ] ;
        state ^= ( 1 << pozitie ) ;
        prev = pozitie ;
        pozitie = urm ;
    }
    FORNBACK ( i , sz , 1 ) {
        cout << sol [ i ] ;
    }
    cout << '\n' ;
    return 0;
}