Advertisement
Guest User

Untitled

a guest
Dec 9th, 2019
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.57 KB | None | 0 0
  1.  
  2. #define _CRT_SECURE_NO_WARNINGS
  3. #define _CRT_DISABLE_PERFCRIT_LOCKS
  4. #include <iostream>
  5. #include<algorithm>
  6. #include<vector>
  7. #include<map>
  8. #include<set>
  9. #include<queue>
  10. #include<bitset>
  11.  
  12. using namespace std;
  13.  
  14. typedef long long ll;
  15.  
  16. const ll IN = ll(1e9);
  17.  
  18. vector<int> w;
  19. int n, a;
  20. ll test(bitset<20> a) {
  21. ll s = 0;
  22. for (int j = 0; j < n; j++) {
  23. if (a[j])
  24. s += w[j];
  25. else
  26. s -= w[j];
  27.  
  28. }
  29. return abs(s);
  30. }
  31. ll binpow(int a, int n) {
  32. if (n == 0)
  33. return 1;
  34. if (n % 2 == 1)
  35. return binpow(a, n - 1) * a;
  36. else {
  37. ll b = binpow(a, n / 2);
  38. return b * b;
  39. }
  40. }
  41. string ans = "";
  42. string a1 = "";
  43. string a2 = "";
  44. vector<vector<int>> temp(1001, vector<int>(1001, 2));
  45. int Solve(int a, int b, int x, int y) {
  46. if (x >= n && y >= n) {
  47. return 1;
  48. }
  49. if (temp[x][y] == 2) {
  50. if (abs(a - b) > 1) {
  51. temp[x][y] = 0;
  52. return 0;
  53. }
  54. else {
  55. int t1 = 0;
  56. if (x < n) {
  57. if (a1[x] == '1')
  58. t1 = Solve(a, b + 1, x + 1, y);
  59. else
  60. t1 = Solve(a + 1, b, x + 1, y);
  61. }
  62. if (t1) {
  63. ans += "1";
  64. return 1;
  65. }
  66. int t2 = 0;
  67. if (y < n) {
  68. if (a2[y] == '1')
  69. t2 = Solve(a, b + 1, x, y + 1);
  70. else
  71. t2 = Solve(a + 1, b, x, y + 1);
  72. }
  73. if (t2) {
  74. ans += "2";
  75. return 1;
  76. }
  77. temp[x][y] = 0;
  78. return 0;
  79. }
  80. }
  81. else
  82. return temp[x][y];
  83.  
  84. }
  85.  
  86.  
  87. int main()
  88. {
  89.  
  90. cin >> n;
  91. cin >> a1;
  92. cin >> a2;
  93. bool s = Solve(0, 0, 0, 0);
  94. if (s) {
  95. reverse(ans.begin(), ans.end());
  96. cout << ans;
  97. }
  98. else
  99. cout << "Impossible";
  100. //system("pause");
  101. return 0;
  102. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement