Cod sursa(job #3295900)

Utilizator mircea_007Mircea Rebengiuc mircea_007 Data 9 mai 2025 17:09:25
Problema ADN Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.96 kb
#include <fstream>

#include <vector>
#include <algorithm>

using ll = long long;
constexpr int INF = 1e9;
constexpr int MOD = 1e9 + 9;

struct ZP {
  int x;
  constexpr ZP( int x = 0 ): x(x % MOD) {}
  ZP( ll x ): x(x % MOD) {}
  bool operator == ( const ZP& that ) const { return x == that.x; }

  ZP operator *= ( const ZP& that ) { return *this = ZP(x * (ll)that.x); }
  ZP operator += ( const ZP& that ) {
    x += that.x;
    if( x >= MOD )
      x -= MOD;
    return *this;
  }
  ZP operator -= ( const ZP& that ) {
    x += MOD - that.x;
    if( x >= MOD )
      x -= MOD;
    return *this;
  }

  ZP operator * ( const ZP& that ) const { return ZP(*this) *= that; }
  ZP operator + ( const ZP& that ) const { return ZP(*this) += that; }
  ZP operator - ( const ZP& that ) const { return ZP(*this) -= that; }
};

constexpr ZP BASE = 17;
constexpr ZP IBASE = int((1e9 + 10) / 17);

ZP pibase( int n ) {
  static std::vector<ZP> vals(1, 1);
  for( int i = vals.size(); i <= n; i++ )
    vals.push_back( vals.back() * IBASE );
  return vals[n];
}

struct Axel {
  std::vector<int> str;
  std::vector<ZP> sp;
  Axel() = default;
  Axel( const std::string &_str ): str(_str.begin(), _str.end()), sp(str.size() + 1, 0) {
    ZP pb = 1;
    for( int i = 0; i < (int)str.size(); i++ ){
      sp[i + 1] = sp[i] + pb * ZP(str[i]);
      pb *= BASE;
    }
  }

  int size() const { return (int)str.size(); }
  ZP hash( int st, int dr ) const { return pibase( st ) * (sp[dr + 1] - sp[st]); }
};

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

int main() {
  int n;
  fin >> n;

  std::vector<Axel> words;
  for( int i = 0; i < n; i++ ){
    std::string str;
    fin >> str;
    words.emplace_back( str );
  }

  {// first, check for full overlap, remove useless
    std::vector<bool> good(n, true);
    for( int i = 0; i < n; i++ )
      for( int j = 0; j < n; j++ ){
        if( (int)words[i].size() >= (int)words[j].size() )
          continue;

        bool shit = false;
        ZP wi = words[i].hash( 0, (int)words[i].size() - 1 );
        for( int delta = 0; delta + (int)words[i].size() - 1 < (int)words[j].size(); delta++ )
          shit |= (wi == words[j].hash( delta, delta + (int)words[i].size() - 1 ));

        if( shit )
          good[i] = false;
      }

    int sp = 0;
    for( int i = 0; i < n; i++ )
      if( good[i] )
        words[sp++] = words[i];
    words.resize( n = sp );
  }

  // now try sticking shit together
  std::vector<std::vector<int>> adj(n, std::vector<int>(n));
  for( int i = 0; i < n; i++ )
    for( int j = 0; j < n; j++ ){
      int maxlen = std::min( (int)words[i].size(), (int)words[j].size() );

      for( int len = 0; len <= maxlen; len++ )
        if( words[i].hash( (int)words[i].size() - len, (int)words[i].size() - 1 ) == words[j].hash( 0, len - 1 ) )
          adj[i][j] = (int)words[j].size() - len;
    }

  // now stick everything together
  int p2 = (1 << n);
  std::vector<std::vector<int>> minlen(p2, std::vector<int>(n, +INF));
  std::vector<std::vector<int>> prev(p2, std::vector<int>(n));

  for( int i = 0; i < n; i++ )
    minlen[1 << i][i] = (int)words[i].size();

  for( int mask = 0; mask < p2; mask++ )
    for( int i = 0; i < n; i++ )
      for( int j = 0; j < n; j++ ){
        int aux = minlen[mask][i] + adj[i][j];
        int nmask = (mask | (1 << j));

        if( aux < minlen[nmask][j] ){
          minlen[nmask][j] = aux;
          prev[nmask][j] = i;
        }
      }

  std::vector<int> sol; {
    int mask = p2 - 1, u = 0;
    for( int i = 0; i < n; i++ )
      if( minlen[mask][i] < minlen[mask][u] )
        u = i;

    while( mask ){
      sol.push_back( u );

      int next = prev[mask][u];
      mask -= (1 << u);
      u = next;
    }

    std::reverse( sol.begin(), sol.end() );
  }

  std::string ret(words[sol[0]].str.begin(), words[sol[0]].str.end());
  for( int i = 1; i < n; i++ ){
    int a = sol[i - 1], b = sol[i];
    ret.insert( ret.end(), words[b].str.end() - adj[a][b], words[b].str.end() );
  }

  fout << ret << std::endl;
  return 0;
}