Advertisement
esraa_syam

string 2

Feb 25th, 2025
2,939
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.98 KB | None | 0 0
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3.  
  4. #define nl "\n"
  5. #define ll long long
  6. #define mod  1'000'000'007
  7. #define all(v) v.begin(), v.end()
  8. #define rall(v) v.rbegin(), v.rend()
  9. #define sz(v) (int) v.size()
  10.  
  11. template<typename T = int>
  12. istream &operator>>(istream &in, vector<T> &v) {
  13.     for (auto &x: v) in >> x;
  14.     return in;
  15. }
  16.  
  17. template<typename T = int>
  18. ostream &operator<<(ostream &out, const vector<T> &v) {
  19.     for (const T &x: v) out << x << " ";
  20.     return out;
  21. }
  22.  
  23. void Sira() {
  24.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  25. #ifndef ONLINE_JUDGE
  26.     freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
  27. #endif
  28. }
  29.  
  30. int n;
  31. vector < string > words, ans;
  32. vector < int > word_mask;
  33.  
  34. int used_char = 0;
  35.  
  36. bool rec(int idx , int cnt) {
  37.     if (cnt == 5) return true;
  38.  
  39.     if (n - idx < 5 - cnt) return false;
  40.  
  41.     for (int i = idx ; i < n ; i++) {
  42.         if (!(used_char & word_mask[i])) {
  43.             used_char |= word_mask[i];
  44.             ans.push_back(words[i]);
  45.             if (rec(i + 1, cnt + 1)) return true;
  46.             ans.pop_back();
  47.             used_char ^= word_mask[i];
  48.         }
  49.     }
  50.  
  51.     return false;
  52.  
  53. }
  54.  
  55. void solve() {
  56.     int words_size;
  57.     cin >> words_size;
  58.  
  59.     vector < string > v(words_size);
  60.  
  61.     cin >> v;
  62.  
  63.     set < string > st;
  64.  
  65.     for(auto & word: v) {
  66.         st.insert(word);
  67.         if (sz(word) == 5 && sz(st) == 5) {
  68.             words.push_back(word);
  69.         }
  70.         st.clear();
  71.     }
  72.  
  73.     n = sz(words);
  74.  
  75.     word_mask.resize(n);
  76.  
  77.  
  78.     for(int i = 0; i < n; i++) {
  79.         int mask = 0;
  80.         for (char c : words[i]) mask |= (1 << (c - 'a'));
  81.         word_mask[i] = mask;
  82.     }
  83.  
  84.     if (!rec(0, 0)) {
  85.         cout << -1 << nl;
  86.         return;
  87.     }
  88.  
  89.     for (string &s : ans) cout << s << " ";
  90.     cout << nl;
  91.    
  92.  
  93. }
  94.  
  95. int main() {
  96.     Sira();
  97.     int t = 1;
  98.     // cin >> t;
  99.     while (t--) {
  100.         solve();
  101.     }
  102.     return 0;
  103. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement