Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include "bits/stdc++.h"
- //#include "geometry.h"
- //#include "data_structure.h"
- using namespace std;
- using namespace chrono;
- #define all(a) a.begin(), a.end()
- #define allr(a) a.rbegin(), a.rend()
- #define sqrt(x) sqrtl(x)
- mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
- typedef long long ll;
- typedef double ld;
- struct Node {
- ll go[2];
- bool terminal = false;
- };
- const ll Maxn = 1e5;
- vector<Node> trie[Maxn];
- void add(string& s) {
- ll v = 0;
- if (trie[s.size()].size()==0) {
- trie[s.size()].push_back(Node());
- }
- for (ll i = 0; i < (ll)s.size(); i++) {
- ll level = s[i] - '0';
- if (trie[s.size()][v].go[level] == 0) {
- trie[s.size()].push_back(Node());
- trie[s.size()][v].go[level] = trie[s.size()].size() - 1;
- }
- v = trie[s.size()][v].go[level];
- }
- trie[s.size()][v].terminal = true;
- }
- map<string, string> ans,out;
- void dfs(ll v, string hash,string d,ll j) {
- bool flag;
- flag = true;
- ll ct = 0;
- for (ll i = 0; i < 2; i++) {
- ll deb = trie[j][v].go[i];
- if (trie[j][v].go[i] != 0) {
- ct++;
- }
- }
- if (ct == 2) {
- flag = false;
- }
- for (ll i = 0; i < 2; i++) {
- if (trie[j][v].go[i] != 0) {
- char c = i + '0';
- if (flag) {
- dfs(trie[j][v].go[i], hash + '?', d + c, j);
- }
- else {
- dfs(trie[j][v].go[i], hash + c, d + c, j);
- }
- }
- }
- if (trie[j][v].terminal) {
- ans[hash] = d;
- out[d] = hash;
- }
- return;
- }
- signed main() {/*
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif*/
- srand(time(NULL));
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- ll n;
- cin >> n;
- vector<string> in;
- set<ll> siz;
- for (ll i = 0; i < n; i++) {
- string s;
- cin >> s;
- siz.insert(s.size());
- in.push_back(s);
- add(s);
- }
- for (auto it = siz.begin(); it != siz.end(); it++) {
- dfs(0, "", "", *it);
- }
- for (string i : in) {
- cout << out[i] << endl;
- }
- cout.flush();
- ll q;
- cin >> q;
- for (ll i = 0; i < q; i++) {
- string s;
- cin >> s;
- cout << ans[s] << endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment