Advertisement
bibaboba12345

Untitled

Dec 30th, 2022
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.48 KB | None | 0 0
  1. // clang-format off
  2. #define _CRT_SECURE_NO_WARNINGS
  3. #include <iostream>
  4. #include <iomanip>
  5. #include <bitset>
  6. #include <vector>
  7. #include <algorithm>
  8. #include <random>
  9. #include <map>
  10. #include <string>
  11. #include <set>
  12. #include <deque>
  13. #include <string>
  14. #include <cassert>
  15.  
  16. using namespace std;
  17. const int N = 2e5 + 7;
  18.  
  19. struct Word {
  20. string s;
  21. int cnt[26];
  22. void init() {
  23. for (int i = 0; i < 26; i++) {
  24. cnt[i] = 0;
  25. }
  26. for (auto u : s) {
  27. cnt[u - 'a'] ++;
  28. }
  29. }
  30. };
  31.  
  32. set<int> poss_masks;
  33. vector<int> sorted;
  34.  
  35. int GetInd(int mask) {
  36. if (*(lower_bound(sorted.begin(), sorted.end(), mask)) != mask) {
  37. return -1;
  38. }
  39. return lower_bound(sorted.begin(), sorted.end(), mask) - sorted.begin();
  40. }
  41.  
  42. bool can(Word& a, Word& b) {
  43. for (int i = 0; i < 26; i++) {
  44. if (a.cnt[i] > b.cnt[i]) {
  45. return 0;
  46. }
  47. }
  48. return 1;
  49. }
  50.  
  51. vector<string> s, answ;
  52.  
  53. vector<Word> dict[N];
  54.  
  55. int n;
  56.  
  57. signed main() {
  58. #ifdef _DEBUG
  59. freopen("input.txt", "r", stdin);
  60. #else
  61. std::ios::sync_with_stdio(false);
  62. cin.tie(0);
  63. #endif
  64. cin >> n;
  65. s.resize(n);
  66. for (int i = 0; i < n; i++) {
  67. cin >> s[i];
  68. int mask = 0;
  69. for (auto u : s[i]) {
  70. mask |= (1 << (u - '0'));
  71. }
  72. poss_masks.insert(mask);
  73. }
  74. for (auto u : poss_masks) {
  75. sorted.push_back(u);
  76. }
  77. for(int i = 0; i < n; i++){
  78. int mask = 0;
  79. for (auto u : s[i]) {
  80. mask |= (1 << (u - '0'));
  81. }
  82. int ind = GetInd(mask);
  83. Word kek;
  84. kek.s = s[i];
  85. kek.init();
  86. dict[ind].push_back(kek);
  87. }
  88. int q;
  89. cin >> q;
  90. for (int I = 0; I < q; I++) {
  91. answ.clear();
  92. string s;
  93. cin >> s;
  94. int mask = 0;
  95. for (auto u : s) {
  96. mask |= (1 << (u - '0'));
  97. }
  98. Word kek;
  99. kek.s = s;
  100. kek.init();
  101. for (int msk2 = mask; msk2 > 0; msk2--, msk2 &= mask) {
  102. int ind = GetInd(msk2);
  103. if (ind == -1) {
  104. continue;
  105. }
  106.  
  107. for (auto& w : dict[ind]) {
  108. if (can(w, kek)) {
  109. answ.push_back(w.s);
  110. }
  111. }
  112. }
  113. sort(answ.begin(), answ.end());
  114. cout << answ.size() << "\n";
  115. for (auto u : answ) {
  116. cout << u << "\n";
  117. }
  118. }
  119.  
  120. }
  121.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement