fork download 
  1. #include <cstdio>
  2.  
  3. #pragma comment(linker, "/STACK:16777216")
  4.  
  5. const int maxn=5000;
  6.  
  7. char s1[maxn],s2[maxn],ans[maxn];
  8. int df1[maxn], df2[maxn];
  9.  
  10. char pr[1024][1024];
  11. void calc_diff(char *s, int *diff, int n){
  12.  
  13.     diff[0]=0;
  14.  
  15.     for(int i=1; i<=n; ++i){
  16.         diff[i]= (s[i-1]=='0') ? diff[i-1]+1 : diff[i-1]-1;
  17.     }
  18.  
  19. }
  20.  
  21. int n;
  22. void dfs(int i, int j){
  23.     if(i>=n && j>=n){
  24.         return;
  25.     }
  26.  
  27.     int diff=df1[i]+df2[j];
  28.  
  29.     if(i<n &&   !pr[i+1][j] && (    (diff<1 && s1[i]=='0') || (diff>-1 && s1[i]=='1')   )  ){
  30.         pr[i+1][j]='1';
  31.         dfs(i+1, j);
  32.     }
  33.  
  34.     if(    j<n && !pr[i][j+1] && (    (diff<1 && s2[j]=='0') || (diff>-1 && s2[j]=='1'   )   )   ){
  35.         pr[i][j+1]='2';
  36.         dfs(i, j+1);
  37.  
  38.     }
  39.  
  40. }
  41. int main()
  42. {
  43.     scanf("%d", &n);
  44.  
  45.     scanf("%s", s1);
  46.     scanf("%s", s2);
  47.  
  48.     calc_diff(s1, df1, n);
  49.     calc_diff(s2, df2, n);
  50.  
  51.  
  52.  
  53.  
  54.     dfs(0, 0);
  55.  
  56.     if(pr[n][n]==0){
  57.         printf("Impossible");
  58.         return 0;
  59.     }
  60.  
  61.     ans[(n<<1)]='\0';
  62.     for(int i=(n<<1)-1, a=n, b=n; i>=0; --i){
  63.         ans[i]=pr[a][b];
  64.         if(ans[i]=='1'){
  65.             --a;
  66.         }
  67.         else{
  68.             --b;
  69.         }
  70.     }
  71.  
  72.     printf("%s", ans);
  73.     return 0;
  74. }
Success #stdin #stdout 0s 16312KB
comments (?)
stdin 
4
0011
0110
stdout 
22121112
https://ideone.com/tm1TcB
language:
C++14 (clang 8.0)
created:
6 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!