ivnikkk

Untitled

Feb 13th, 2022
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.08 KB | None | 0 0
  1.  
  2. #define _CRT_SECURE_NO_WARNINGS
  3. #include "bits/stdc++.h"
  4. //#include "geometry.h"
  5. //#include "data_structure.h"
  6. using namespace std;
  7. using namespace chrono;
  8. #define all(a) a.begin(), a.end()
  9. #define allr(a) a.rbegin(), a.rend()
  10. #define sqrt(x) sqrtl(x)
  11. mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
  12. typedef long long ll;
  13. typedef double ld;
  14. struct Node {
  15.     ll go[2];
  16.     bool terminal = false;
  17. };
  18. const ll Maxn = 1e5;
  19. vector<Node> trie[Maxn];
  20. void add(string& s) {
  21.     ll v = 0;
  22.     if (trie[s.size()].size()==0) {
  23.         trie[s.size()].push_back(Node());
  24.     }
  25.     for (ll i = 0; i < (ll)s.size(); i++) {
  26.         ll level = s[i] - '0';
  27.         if (trie[s.size()][v].go[level] == 0) {
  28.             trie[s.size()].push_back(Node());
  29.             trie[s.size()][v].go[level] = trie[s.size()].size() - 1;
  30.         }
  31.         v = trie[s.size()][v].go[level];
  32.     }
  33.     trie[s.size()][v].terminal = true;
  34. }
  35. map<string, string> ans,out;
  36. void dfs(ll v, string hash,string d,ll j) {
  37.     bool flag;
  38.     flag = true;
  39.     ll ct = 0;
  40.     for (ll i = 0; i < 2; i++) {
  41.         ll deb = trie[j][v].go[i];
  42.         if (trie[j][v].go[i] != 0) {
  43.             ct++;
  44.         }
  45.     }
  46.     if (ct == 2) {
  47.         flag = false;
  48.     }
  49.     for (ll i = 0; i < 2; i++) {
  50.         if (trie[j][v].go[i] != 0) {
  51.             char c = i + '0';
  52.             if (flag) {
  53.                 dfs(trie[j][v].go[i], hash + '?', d + c, j);
  54.             }
  55.             else {
  56.                 dfs(trie[j][v].go[i], hash + c, d + c, j);
  57.             }
  58.         }
  59.  
  60.     }
  61.     if (trie[j][v].terminal) {
  62.         ans[hash] = d;
  63.         out[d] = hash;
  64.     }
  65.     return;
  66. }
  67. signed main() {/*
  68. #ifdef _DEBUG
  69.     freopen("input.txt", "r", stdin);
  70.     freopen("output.txt", "w", stdout);
  71. #endif*/
  72.     srand(time(NULL));
  73.     ios_base::sync_with_stdio(false);
  74.     cin.tie(nullptr);
  75.     cout.tie(nullptr);
  76.     ll n;
  77.     cin >> n;
  78.     vector<string> in;
  79.     set<ll> siz;
  80.     for (ll i = 0; i < n; i++) {
  81.         string s;
  82.         cin >> s;
  83.         siz.insert(s.size());
  84.         in.push_back(s);
  85.         add(s);
  86.     }
  87.     for (auto it = siz.begin(); it != siz.end(); it++) {
  88.         dfs(0, "", "", *it);
  89.     }
  90.     for (string i : in) {
  91.         cout << out[i] << endl;
  92.     }
  93.     cout.flush();
  94.     ll q;
  95.     cin >> q;
  96.     for (ll i = 0; i < q; i++) {
  97.         string s;
  98.         cin >> s;
  99.         cout << ans[s] << endl;
  100.     }
  101. }
Advertisement
Add Comment
Please, Sign In to add comment