fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long long n,k;
  4. string s;
  5. void backtrack(long long pos, long long cnt)
  6. {
  7.     if(pos==n+1)
  8.     {
  9.         for (long long i=1; i<s.size(); i++)
  10.         {
  11.             cout << s[i];
  12.         }
  13.         cout << "\n";
  14.         return;
  15.     }
  16.     if(pos==1)
  17.     {
  18.         for (long long i=0; i<=1; i++)
  19.         {
  20.             s[2*pos-1]=char(i+'0');
  21.             s[2*pos]=' ';
  22.  
  23.             if(i==0)
  24.             {
  25.                 if(k-cnt<=(n-pos)/2+(n-pos)%2)
  26.                 {
  27.                     backtrack(pos+1,cnt);
  28.                 }
  29.             }
  30.             else
  31.             {
  32.                 if(cnt+1<=k)
  33.                 {
  34.                     backtrack(pos+1,cnt+1);
  35.                 }
  36.             }
  37.         }
  38.         return;
  39.     }
  40.     else
  41.     {
  42.         long long l1 = 0;
  43.         long long r1 = !(cnt==k && s[2*(pos-1)-1]=='0');
  44.  
  45.         long long l2 = (s[2*(pos-1)-1]=='0' &&
  46.                         (n-pos)/2+(n-pos)%2 < max(0ll,k-cnt));
  47.  
  48.         long long r2 = !(s[2*(pos-1)-1]=='1' &&
  49.                          (n-pos)/2 < max(0ll,k-cnt));
  50.  
  51.         long long l = max(l1,l2);
  52.         long long r = min(r1,r2);
  53.  
  54.         for(long long i=l; i<=r; i++)
  55.         {
  56.             s[2*pos-1]=char(i+'0');
  57.             s[2*pos]=' ';
  58.  
  59.             if(i==0)
  60.             {
  61.                 backtrack(pos+1,cnt);
  62.             }
  63.             else if(i==1 && s[2*(pos-1)-1]=='0')
  64.             {
  65.                 backtrack(pos+1,cnt+1);
  66.             }
  67.             else
  68.             {
  69.                 backtrack(pos+1,cnt);
  70.             }
  71.         }    }
  72. }
  73. int main()
  74. {
  75.     ios_base::sync_with_stdio(0);
  76.     cin.tie(0);
  77.     cin >> n >> k;
  78.     for (long long i=1; i<=2*n; i++)
  79.     {
  80.         s+=' ';
  81.     }
  82.     backtrack(1,0);
  83. }
  84.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/kIbAeG
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++14 (gcc 8.3)

					

					

						
created:
								
						
13 hours 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!