Cod sursa(job #2243287)

Utilizator VintilaMMMVintila Mircea VintilaMMM Data 20 septembrie 2018 11:40:51
Problema ADN Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.17 kb
// https://infoarena.ro/problema/adn

#include <cstdlib>
#include <iomanip>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>

//#define DEBUG

std::ifstream in("adn.in");
std::ofstream out("adn.out");

std::vector<std::string> adn;
std::string::size_type* adnmat;
unsigned int n;

int main()
{
    in >> n;
    std::string::size_type maxstr = 0;

    {
        std::string temp;
        adn.reserve(n);

        for(unsigned int i = 0; i < n; i++)
        {
            in >> temp;
            maxstr += temp.size();
            adn.push_back(temp);
        }

        temp.clear();
    }

    adnmat = (std::string::size_type*)calloc(n * n, sizeof(*adnmat));

    for(unsigned int i = 0; i < n - 1; i++)
    {
        for(unsigned int j = i + 1; j < n; j++)
        {
            if(adn[i].find(adn[j]) != std::string::npos)
                adnmat[i * n + j] = std::string::npos;
            else
                for(std::string::size_type d = 1; d <= adn[i].size(); d++)
                    if(adn[j].find(adn[i].substr(adn[i].size() - d)) == 0)
                        adnmat[i * n + j] = d;

            if(adn[j].find(adn[i]) != std::string::npos)
                adnmat[j * n + i] = std::string::npos;
            else
                for(std::string::size_type d = 1; d <= adn[j].size(); d++)
                    if(adn[i].find(adn[j].substr(adn[j].size() - d)) == 0)
                        adnmat[j * n + i] = d;
        }
    }

    #ifdef DEBUG
    for(unsigned int i = 0; i < n; i++)
    {
        for(unsigned int j = 0; j < n; j++)
            if(adnmat[i * n + j] != std::string::npos)
                out << std::setw(5) << adnmat[i * n + j];
            else
                out << " npos";

        out << std::endl;
    }
    #endif // DEBUG

    unsigned int over;
    unsigned int mover = 0;
    std::vector<unsigned int> ovec;
    std::vector<unsigned int> movec;

    ovec.reserve(n);
    movec.reserve(n);
    for(unsigned int i = 0; i < n; i++)
        ovec.push_back(i);

    do
    {
        over = 0;
        for(unsigned int i = 0; i < n - 1; i++)
            if(adnmat[ovec[i] * n + ovec[i + 1]] != std::string::npos)
                over += adnmat[ovec[i] * n + ovec[i + 1]];
            else
                over += adn[ovec[i]].size();

        if(over >= mover)
        {
            mover = over;
            movec = ovec;
        }
    }
    while(std::next_permutation(ovec.begin(), ovec.end()));

    #ifdef DEBUG
    for(unsigned int i = 0; i < n; i++)
        out << movec[i] + 1 << ' ';
    out << std::endl;
    #endif // DEBUG

    std::string fin;
    fin.reserve(maxstr);

    fin += adn[movec[0]];
    for(unsigned int i = 1; i < n; i++)
        if(adnmat[movec[i - 1] * n + movec[i]] != std::string::npos)
            fin += adn[movec[i]].substr(adnmat[movec[i - 1] * n + movec[i]]);

    out << fin << std::endl;
    #ifdef DEBUG
    out << "AGATAGATGATAACCGCGCAGTGATGAGATGGGGATATAAAAACTTTTTT " << (fin == (std::string)"AGATAGATGATAACCGCGCAGTGATGAGATGGGGATATAAAAACTTTTTT") << std::endl;
    #endif

    in.close();
    out.close();
    return 0;
}