Submission #34755826

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
#include <iostream>
#include <sstream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <numeric>
#include <algorithm>
#include <bitset>
#include <complex>
#include <array>
#include <list>
#include <stack>
#include <valarray>

using namespace std;

typedef unsigned uint;
typedef long long Int;
typedef unsigned long long UInt;

const int INF = 1001001001;
const Int INFLL = 1001001001001001001LL;

template <typename T>
void pv(T a, T b)
{
  for (T i = a; i != b; ++i)
    cout << *i << " ";
  cout << endl;
}
template <typename T>
void chmin(T &a, T b)
{
  if (a > b)
    a = b;
}
template <typename T>
void chmax(T &a, T b)
{
  if (a < b)
    a = b;
}
int in()
{
  int x;
  scanf("%d", &x);
  return x;
}
double fin()
{
  double x;
  scanf("%lf", &x);
  return x;
}
Int lin()
{
  Int x;
  scanf("%lld", &x);
  return x;
}

const int MAX = 16 * 100050;
int link[MAX][27], nodes = 1;
int ac[MAX];

void add(string s)
{
  int p = 0;
  for (int i = 0; i < (int)s.length(); ++i)
  {
    const int c = s[i] == '_' ? 26 : s[i] - 'a';
    if (link[p][c] == -1)
    {
      link[p][c] = nodes++;
      ac[nodes - 1] = 0;
    }
    p = link[p][c];
  }
  ac[p] = 1;
}

bool match(string s)
{
  int p = 0;
  for (int i = 0; i < (int)s.size(); ++i)
  {
    const int c = s[i] == '_' ? 26 : s[i] - 'a';
    p = link[p][c];
    if (p == -1)
      return false;
  }
  return ac[p] == 1;
}

vector<string> S;

void search(int u, string s)
{
  if (s.length() >= 3 && u == (1 << (int)S.size()) - 1 && !match(s))
  {
    cout << s << endl;
    exit(0);
  }
  for (int i = 0; i < (int)S.size(); ++i)
  {
    if (u & (1 << i))
    {
      continue;
    }
    int us = u == 0 ? 0 : 1;
    while (s.length() + us + S[i].length() <= 16)
    {
      string ss = s + string(us, '_') + S[i];
      search(u | (1 << i), ss);
      if (u == 0)
        break;
      ++us;
    }
  }
}

int main()
{
  for (int i = 0; i < MAX; ++i)
  {
    fill(link[i], link[i] + 27, -1);
  }
  int N = in();
  int M = in();
  S.resize(N);
  for (int i = 0; i < N; ++i)
  {
    cin >> S[i];
  }
  for (int i = 0; i < M; ++i)
  {
    string t;
    cin >> t;
    add(t);
  }
  search(0, "");
  cout << -1 << endl;
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int in()’:
./Main.cpp:53:8: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   53 |   scanf("%d", &x);
      |   ~~~~~^~~~~~~~~~
./Main.cpp: In function ‘double fin()’:
./Main.cpp:59:8: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   59 |   scanf("%lf", &x);
      |   ~~~~~^~~~~~~~~~~
./Main.cpp: In function ‘Int lin()’:
./Main.cpp:65:8: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   65 |   scanf("%lld", &x);
      |   ~~~~~^~~~~~~~~~~~

Judge Result