Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long LL;
- const int maxn = 17;
- int n, m;
- int a[maxn], b[maxn];
- string e1[maxn], e2[maxn];
- int sum[1 << maxn];
- pair<int, int> dp[1 << maxn];
- unordered_map<string, int> w;
- string element[] = {
- "kong", "H", "He", "Li", "Be", "B", "C", "N", "O", "F", "Ne", "Na", "Mg", "Al", "Si", "P", "S", "Cl", "Ar",
- "K", "Ca", "Sc", "Ti", "V", "Cr", "Mn", "Fe", "Co", "Ni", "Cu", "Zn", "Ga", "Ge", "As", "Se", "Br",
- "Kr", "Rb", "Sr", "Y", "Zr", "Nb", "Mo", "Tc", "Ru", "Rh", "Pd", "Ag", "Cd", "In", "Sn", "Sb", "Te",
- "I", "Xe", "Cs", "Ba", "La", "Ce", "Pr", "Nd", "Pm", "Sm", "Eu", "Gd", "Tb", "Dy", "Ho", "Er", "Tm",
- "Yb", "Lu", "Hf", "Ta", "W", "Re", "Os", "Ir", "Pt", "Au", "Hg", "Tl", "Pb", "Bi", "Po", "At", "Rn",
- "Fr", "Ra", "Ac", "Th", "Pa", "U", "Np", "Pu", "Am", "Cm", "Bk", "Cf", "Es", "Fm"};
- inline int lowbit(int x) {
- return x & -x;
- }
- inline int nextSameHammingWeightNumber(int x) {
- int t = x + lowbit(x);
- return t | (((lowbit(t) / lowbit(x)) >> 1) - 1);
- }
- inline int nextSubMask(int subMask, int mask) {
- return (subMask - 1) & mask;
- }
- int main() {
- #ifdef ExRoc
- freopen("test.txt", "r", stdin);
- #endif // ExRoc
- ios::sync_with_stdio(false);
- for (int i = 1; i <= 100; ++i) {
- w[element[i]] = i;
- }
- cin >> n >> m;
- for (int i = 0; i < n; ++i) {
- cin >> e1[i];
- a[i] = w[e1[i]];
- }
- for (int i = 0; i < m; ++i) {
- cin >> e2[i];
- b[i] = w[e2[i]];
- }
- for (int i = 1; i <= n; ++i) {
- for (int j = (1 << i) - 1; j < (1 << n); j = nextSameHammingWeightNumber(j)) {
- for (int k = 0; k < n; ++k) {
- if ((j & (1 << k)) != 0) {
- sum[j] = sum[j ^ (1 << k)] + a[k];
- break;
- }
- }
- }
- }
- for (int i = 1; i <= n; ++i) {
- for (int j = (1 << i) - 1; j < (1 << n); j = nextSameHammingWeightNumber(j)) {
- dp[j] = {-1, -1};
- for (int k = nextSubMask(j, j); k != 0; k = nextSubMask(k, j)) {
- if (dp[k].first != -1) {
- for (int l = 0; l < m; ++l) {
- if ((dp[k].first & (1 << l)) == 0 && b[l] == sum[j ^ k]) {
- dp[j] = {dp[k].first | (1 << l), k};
- break;
- }
- }
- }
- if (dp[j].first != -1) {
- break;
- }
- }
- }
- }
- if (dp[(1 << n) - 1].first != (1 << m) - 1) {
- cout << "NO" << endl;
- return 0;
- }
- int status = (1 << n) - 1;
- while (status != 0) {
- int pre = dp[status].second;
- bool flag = false;
- for (int i = 0; i < n; ++i) {
- if (((status ^ pre) & (1 << i)) != 0) {
- if (flag) {
- cout << "+";
- }
- flag = true;
- cout << e1[i];
- }
- }
- cout << "->";
- for (int i = 0; i < m; ++i) {
- if (((dp[status].first ^ dp[pre].first) & (1 << i)) != 0) {
- cout << e2[i];
- }
- }
- cout << endl;
- status = dp[status].second;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement