Forum Comments

2D Arrays 05/01/2020
In Java Question Bank
2D Arrays 05/01/2020
In Java Question Bank
Senior2019-Set 4 - Recursive Functions and CNS 4
In ACSL Contest Prep
colinzhao777
Nov 17, 2019
2. E 3. A 12. B
Content media
0
0
Senior2019-Set 3 - Recursive Functions and CNS 3
In ACSL Contest Prep
Senior2019-Set 3 - Recursive Functions and CNS 3
In ACSL Contest Prep
colinzhao777
Nov 11, 2019
0
0
Senior2019-Set 2 - Recursive Functions and CNS 2
In ACSL Contest Prep
colinzhao777
Nov 04, 2019
1. C 2. E 11. C #include <bits/stdc++.h> using namespace std; #define pb push_back #define ii pair<int, int> #define vi vector<int> #define vii vector<ii> #define vs vector<string> #define ll long long #define ull usigned ll #define INF 1000000000 void insert(char a, vector<char> &tree, int pos) { if (tree[pos] == '~') { tree[pos] = a; } else { if (a <= tree[pos]) { insert(a, tree, 2 * pos); } else { insert(a, tree, 2 * pos + 1); } } } bool check(vector<char> a, vector<char> b, int start) { queue<ii> q; int thing = 1; ii temp = ii(thing, start); q.push(temp); vector<bool> visited(a.size() + 1, false); visited[1] = true; while (!q.empty()) { ii u = q.front(); q.pop(); if (u.first * 2 < (int)a.size() && a[u.first * 2] != '~') { if (u.second * 2 < (int)b.size() && b[u.second * 2] != '~') { if (!visited[u.first * 2]) { q.push(ii(u.first * 2, u.second * 2)); visited[u.first * 2] = true; } } else { return false; } } if (u.first * 2 + 1 < (int)a.size() && a[u.first * 2 + 1] != '~') { if (u.second * 2 + 1 < (int)b.size() && b[u.second * 2 + 1] != '~') { if (!visited[u.first * 2 + 1]) { q.push(ii(u.first * 2 + 1, u.second * 2 + 1)); visited[u.first * 2 + 1] = true; } } else { return false; } } } return true; } int main() { string a, b; cin >> a >> b; a = a.substr(0, a.length() - 1); vector<char> smallTree(4000, '~'), bigTree(4000, '~'); for (int i = 0; i < (int)a.length(); i++) { insert(a[i], smallTree, 1); } for (int i = 0; i < (int)b.length(); i++) { insert(b[i], bigTree, 1); } vector<char> ans; for (int i = 1; i <= (int)b.length(); i++) { if (bigTree[i] != '~' && check(smallTree, bigTree, i)) ans.pb(bigTree[i]); } for (auto it : ans) { cout << it << ", "; } if (ans.size() == 0) cout << "NONE"; cout << endl; }
0
0
c
colinzhao777
More actions