fork download
copy 
  1. // #pragma GCC optimize("Ofast,unroll-loops")
  2. #include <algorithm>
  3. #include <bitset>
  4. #include <cassert>
  5. #include <chrono>
  6. #include <climits>
  7. #include <cmath>
  8. #include <cstdint>
  9. #include <deque>
  10. #include <forward_list>
  11. #include <fstream>
  12. #include <functional>
  13. #include <iomanip>
  14. #include <iostream>
  15. #include <list>
  16. #include <map>
  17. #include <numeric>
  18. #include <queue>
  19. #include <random>
  20. #include <set>
  21. #include <sstream>
  22. #include <stack>
  23. #include <string>
  24. #include <unordered_map>
  25. #include <unordered_set>
  26. #include <vector>
  27.  
  28. using namespace std;
  29.  
  30. // #pragma GCC target("avx,avx2,fma")
  31.  
  32. #define all(x) std::begin(x), std::end(x)
  33. #define isz(x) (int)std::size(x)
  34.  
  35. const auto ready = []() {
  36.   std::ios_base::sync_with_stdio(0);
  37.   std::cin.tie(0);
  38.   std::cout.tie(0);
  39.   std::cout << std::fixed << std::setprecision(12);
  40.   return 1;
  41. };
  42.  
  43. const auto TEST = []() { freopen("in.txt", "r", stdin); };
  44.  
  45. using ll = long long;
  46. using ull = unsigned long long;
  47. using ld = long double;
  48.  
  49. template <typename C>
  50. void reuniq(C& c) {
  51.   c.erase(unique(all(c)), end(c));
  52. }
  53.  
  54. template <typename C, typename X>
  55. int lowpos(const C& c, X x) {
  56.   return int(lower_bound(all(c), x) - begin(c));
  57. }
  58.  
  59. template <typename C, typename X>
  60. int uppos(const C& c, X x) {
  61.   return int(upper_bound(all(c), x) - begin(c));
  62. }
  63.  
  64. template <typename X, typename Y>
  65. X& remin(X& x, const Y& y) {
  66.   return x = (y < x) ? y : x;
  67. }
  68.  
  69. template <typename X, typename Y>
  70. X& remax(X& x, const Y& y) {
  71.   return x = (x < y) ? y : x;
  72. }
  73.  
  74. void Solve() {
  75.   int n, q, w;
  76.   cin >> n >> q >> w;
  77.   vector<pair<string, int>> a(n);
  78.   for (int i = 0; i < n; ++i) {
  79.     auto& [s, j] = a[i];
  80.     cin >> s;
  81.     j = i + 1;
  82.   }
  83.   sort(all(a));
  84.   // пусть маска означает какие буквы есть в слове
  85.   // сохраним для каждой маски индекс строки такой \
  86.      что для какой то из подмасок существует строка \
  87.      из массива а которая представима этой маской
  88.   vector<int> dp(1 << 20, n);
  89.   for (int i = 0; i < n; ++i) {
  90.     const auto& [s, _] = a[i];
  91.     bitset<20> mask = 0;
  92.     for (auto c : s) mask |= 1 << (c - 'a');
  93.     // здесь у нас база
  94.     remin(dp[(mask).to_ulong()], i);
  95.   }
  96.   for (int i = 0; i < (1 << 20); ++i) {
  97.     for (int j = 0; j < 20; ++j) {
  98.       // ставим текущий бит -> получаем надмаску \
  99.          тем самым делаем условие 86 строки
  100.       remin(dp[i | (1 << j)], dp[i]);
  101.     }
  102.   }
  103.   while (q --> 0) {
  104.     string s;
  105.     cin >> s;
  106.     bitset<20> mask = 0;
  107.     for (auto c : s) mask |= 1 << (c - 'a');
  108.     // берем ~маску так как нам нужен ответ не для самой маски(так как это будет полное пересечение) \
  109.        а пытаемся найти любую маску которая есть в массиве \
  110.        что у нас и предпосчитано в дп
  111.     cout << (dp[(~mask).to_ulong()] == n ? -1 : a[dp[(~mask).to_ulong()]].second) << '\n';
  112.   }
  113. }
  114.  
  115. signed main() {
  116.   ready();
  117.   Solve();
  118. }
Success #stdin #stdout 0.06s 7328KB
comments (?)
stdin
copy 
4 3 20
cat
bank
bed
gate
joke
mail
team
stdout
copy 
1
3
-1
https://ideone.com/1hwv8C
language:
C++ (gcc 8.3)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!