fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n;
  4. char p1[1002], p2[1002];
  5. string dp[1002][1002][2][2];
  6. string f(int i, int j,int u, int v,string s) {
  7. 	if(i==n && j == n) return s;
  8. 	if(dp[i][j][u][v]!="") return dp[i][j][u][v];
  9. 	if(i==n) {
  10. 		if(u > v && j < n){
  11. 			if(p2[j] == '1') return dp[i][j][u][v] = f(i, j+1, 0, 0, s+'2');
  12. 			else return dp[i][j][u][v] = "";
  13. 		}
  14. 		if(u < v && j < n){
  15. 			if(p2[j] == '0') return dp[i][j][u][v] = f(i, j+1, 0, 0, s+'2');
  16. 			else return dp[i][j][u][v] = "";
  17. 		}
  18. 		if(u == v && j < n){
  19. 			if(p2[j] == '0') return dp[i][j][u][v] = f(i, j+1, 1, 0, s+'2');
  20. 			else return dp[i][j][u][v] = f(i, j+1, 0, 1, s+'2');
  21. 		}
  22. 	}
  23. 	if(j==n) {
  24. 		if(u > v && i < n){
  25. 			if(p1[i] == '1') return dp[i][j][u][v] = f(i+1, j, 0, 0, s+'1');
  26. 			else return dp[i][j][u][v] = "";
  27. 		}
  28. 		if(u < v && i < n){
  29. 			if(p1[i] == '0') return dp[i][j][u][v] = f(i+1, j, 0, 0, s+'1');
  30. 			else return dp[i][j][u][v] = "";
  31. 		}
  32. 		if(u == v && i < n){
  33. 			if(p1[i] == '0') return dp[i][j][u][v] = f(i+1, j, 1, 0, s+'1');
  34. 			else return dp[i][j][u][v] = f(i+1, j, 0, 1, s+'1');
  35. 		}
  36. 	}
  37. 	string a,b,c,d;
  38. 	if(u>v) {
  39. 		if(p1[i]=='1') a = f(i+1, j, 0, 0, s+'1');
  40. 		if(p2[j]=='1') b = f(i, j+1, 0, 0, s+'2');
  41. 		if(a.size()>b.size()) return dp[i][j][u][v] = a;
  42. 		else return dp[i][j][u][v] = b;
  43. 	}
  44. 	if(u<v) {
  45. 		if(p1[i]=='0') a = f(i+1, j, 0, 0, s+'1');
  46. 		if(p2[j]=='0') b = f(i, j+1, 0, 0, s+'2');
  47. 		if(a.size()>b.size()) return dp[i][j][u][v] = a;
  48. 		else return dp[i][j][u][v] = b;
  49. 	}
  50. 	if(p1[i]=='0') a = f(i+1, j, 1, 0, s+'1');
  51. 	if(p1[i]=='1') b = f(i+1, j, 0, 1, s+'1');
  52. 	if(p2[j]=='0') c = f(i, j+1, 1, 0, s+'2');
  53. 	if(p2[j]=='1') d = f(i, j+1, 0, 1, s+'2');
  54. 	string str;
  55. 	if(a.size()>b.size()) str = a;
  56. 	else str = b;
  57. 	if(s.size()<c.size()) str = c;
  58. 	if(s.size()<d.size()) str = d;
  59. 	return dp[i][j][u][v] = str;
  60. }
  61.  
  62. int main() {
  63. 	scanf("%d",&n);
  64. 	scanf("%s",&p1);
  65. 	scanf("%s",&p2);
  66. 	//memset(dp, 0, sizeof dp);
  67. 	string ans = f(0,0,0,0,"");
  68. 	if(ans.size()==2*n) cout<<ans<<endl;
  69. 	else cout<<"Impossible\n";
  70. 	return 0;
  71. }
Success #stdin #stdout 0.03s 19160KB
comments (?)
stdin
copy 
4
0011
0110
stdout
copy 
22121121
https://ideone.com/WBy8XA
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!