Advertisement
Dmaxiya

test

Sep 14th, 2023
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.33 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long LL;
  5. const int maxn = 17;
  6. int n, m;
  7. int a[maxn], b[maxn];
  8. string e1[maxn], e2[maxn];
  9. int sum[1 << maxn];
  10. pair<int, int> dp[1 << maxn];
  11. unordered_map<string, int> w;
  12. string element[] = {
  13. "kong", "H", "He", "Li", "Be", "B", "C", "N", "O", "F", "Ne", "Na", "Mg", "Al", "Si", "P", "S", "Cl", "Ar",
  14. "K", "Ca", "Sc", "Ti", "V", "Cr", "Mn", "Fe", "Co", "Ni", "Cu", "Zn", "Ga", "Ge", "As", "Se", "Br",
  15. "Kr", "Rb", "Sr", "Y", "Zr", "Nb", "Mo", "Tc", "Ru", "Rh", "Pd", "Ag", "Cd", "In", "Sn", "Sb", "Te",
  16. "I", "Xe", "Cs", "Ba", "La", "Ce", "Pr", "Nd", "Pm", "Sm", "Eu", "Gd", "Tb", "Dy", "Ho", "Er", "Tm",
  17. "Yb", "Lu", "Hf", "Ta", "W", "Re", "Os", "Ir", "Pt", "Au", "Hg", "Tl", "Pb", "Bi", "Po", "At", "Rn",
  18. "Fr", "Ra", "Ac", "Th", "Pa", "U", "Np", "Pu", "Am", "Cm", "Bk", "Cf", "Es", "Fm"};
  19.  
  20. inline int lowbit(int x) {
  21. return x & -x;
  22. }
  23.  
  24. inline int nextSameHammingWeightNumber(int x) {
  25. int t = x + lowbit(x);
  26. return t | (((lowbit(t) / lowbit(x)) >> 1) - 1);
  27. }
  28.  
  29. inline int nextSubMask(int subMask, int mask) {
  30. return (subMask - 1) & mask;
  31. }
  32.  
  33. int main() {
  34. #ifdef ExRoc
  35. freopen("test.txt", "r", stdin);
  36. #endif // ExRoc
  37. ios::sync_with_stdio(false);
  38.  
  39. for (int i = 1; i <= 100; ++i) {
  40. w[element[i]] = i;
  41. }
  42. cin >> n >> m;
  43. for (int i = 0; i < n; ++i) {
  44. cin >> e1[i];
  45. a[i] = w[e1[i]];
  46. }
  47. for (int i = 0; i < m; ++i) {
  48. cin >> e2[i];
  49. b[i] = w[e2[i]];
  50. }
  51. for (int i = 1; i <= n; ++i) {
  52. for (int j = (1 << i) - 1; j < (1 << n); j = nextSameHammingWeightNumber(j)) {
  53. for (int k = 0; k < n; ++k) {
  54. if ((j & (1 << k)) != 0) {
  55. sum[j] = sum[j ^ (1 << k)] + a[k];
  56. break;
  57. }
  58. }
  59. }
  60. }
  61. for (int i = 1; i <= n; ++i) {
  62. for (int j = (1 << i) - 1; j < (1 << n); j = nextSameHammingWeightNumber(j)) {
  63. dp[j] = {-1, -1};
  64. for (int k = nextSubMask(j, j); k != 0; k = nextSubMask(k, j)) {
  65. if (dp[k].first != -1) {
  66. for (int l = 0; l < m; ++l) {
  67. if ((dp[k].first & (1 << l)) == 0 && b[l] == sum[j ^ k]) {
  68. dp[j] = {dp[k].first | (1 << l), k};
  69. break;
  70. }
  71. }
  72. }
  73. if (dp[j].first != -1) {
  74. break;
  75. }
  76. }
  77. }
  78. }
  79. if (dp[(1 << n) - 1].first != (1 << m) - 1) {
  80. cout << "NO" << endl;
  81. return 0;
  82. }
  83. int status = (1 << n) - 1;
  84. while (status != 0) {
  85. int pre = dp[status].second;
  86. bool flag = false;
  87. for (int i = 0; i < n; ++i) {
  88. if (((status ^ pre) & (1 << i)) != 0) {
  89. if (flag) {
  90. cout << "+";
  91. }
  92. flag = true;
  93. cout << e1[i];
  94. }
  95. }
  96. cout << "->";
  97. for (int i = 0; i < m; ++i) {
  98. if (((dp[status].first ^ dp[pre].first) & (1 << i)) != 0) {
  99. cout << e2[i];
  100. }
  101. }
  102. cout << endl;
  103. status = dp[status].second;
  104. }
  105.  
  106. return 0;
  107. }
  108.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement