fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define Mod 1000000007;
  4. long int ans=0;
  5. bool check(string S1, string S2)    //function to check 2 string partitions are valid or not.
  6. {
  7.     if(S1.length()>S2.length())
  8.     return false;
  9.     if(S2[0]=='0'||S1[0]=='0')          //if first character is 0 return false.
  10.     return false;
  11.     if(count(S1.begin(),S1.end(),'1')>count(S2.begin(),S2.end(),'1')) //if number of 1's in first is larger than 1's in second string
  12.     return false;                                                     //return false;
  13.     return true; //if upper condition is false then return true.
  14. }
  15.  
  16.  
  17. void Partition(string &S,int i,int j,int len=1,string Prev="")//S is actual string, i starting index(of a partition), j is end index. 
  18. {                                                             //len is length of first string partition, prev is previous partition.           
  19.     if(S[i]=='0')  //if first index char is '0' partition is not possible.
  20.     return ;
  21.     if(i==j||j-(i+len)+1<len) //base condition if length of other partition is less than first then return.
  22.     {
  23.     return ;
  24.     }
  25.     for(int k=i;j-(k+len)+1>=len;len++)
  26.     {   
  27.         if(S[k+len]=='0')
  28.         continue;
  29.         if(Prev!="")
  30.         {
  31.             if(check(Prev,S.substr(k,len))) //first checking with prev partition then with second partion.
  32.             {
  33.                 if(check(S.substr(k,len),S.substr(k+len)))
  34.                  {
  35.  
  36.                     ans=(ans+1)%Mod;
  37.                     Prev=S.substr(k,len);// storing Prev 
  38.                     Partition(S,k+len,j,len,Prev); //checking for next partition from k+len with prev partition      
  39.                 }
  40.             }
  41.         }
  42.         else
  43.         {
  44.             if(check(S.substr(k,len),S.substr(k+len)))
  45.                  {
  46.                     ans=(ans+1)%Mod;
  47.                     Prev=S.substr(k,len);
  48.                     Partition(S,k+len,j,len,Prev);        
  49.                 }
  50.         }
  51.  
  52.     }
  53.     return ;
  54. }
  55. int main()
  56. {
  57.  
  58.     int n;   
  59.     string S;
  60.     cin>>n>>S;
  61.     string prev="";
  62.     Partition(S,0,S.length()-1);
  63.     cout<<ans+1<<"\n";
  64. }
Success #stdin #stdout 0s 4492KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/7CwYyE
language:
C++14 (gcc 8.3)
created:
4 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!