Submission #148085

#	Time	Username	Problem	Language	Result	Execution time	Memory
148085		JovanK26	Ljetopica (COI19_ljetopica)	C++14	100 / 100	144 ms	31972 KiB

ljetopica

#include <bits/stdc++.h>
#define mod 1000000007
using namespace std;
int n,k;
string path,a,b;
int power[1001];
inline int add(int i,int j)
{
   if(i+j<0)return i+j+mod;
   if(i+j>=mod)return i+j-mod;
   return i+j;
}
inline int mul(int i,int j)
{
    long long temp=(long long)i*j;
    temp%=mod;
    return temp;
}
void sett()
{
    power[0]=1;
    for(int i=1;i<=n;i++)
    {
        power[i]=mul(2,power[i-1]);
    }
}
pair<int,int> f[1001][1001][2][2];
pair<int,int> solve(int depth,int br,bool chk,bool con,const string &s)
{
   pair<int,int> cur=f[depth][br][chk][con];
   if(cur!=make_pair(-1,-1))return cur;
   if(depth==path.size())return make_pair(br==k,0);
   if(br>k)return make_pair(0,0);
   int way=0;
   int cf=0;
   int sum=0;
   bool bv=s[depth+1]=='1';
   bool mv=(path[depth]=='R' && (br+chk)%2==0)||(path[depth]=='L' && (br+chk)%2==1);
   if(depth==0 && !chk)
   {
       pair<int,int> temp=solve(depth,br,!chk,con,s);
       way=add(way,temp.first);
       sum=add(sum,temp.second);
   }
   if(con)
   {
       if(mv<=bv)
       {
           pair<int,int> temp=solve(depth+1,br,chk,mv==bv,s);
           way=add(way,temp.first);
           sum=add(sum,temp.second);
           if(mv)cf=add(cf,temp.first);
       }
       if(!mv<=bv)
       {
           pair<int,int> temp=solve(depth+1,br+1,chk,!mv==bv,s);
           way=add(way,temp.first);
           sum=add(sum,temp.second);
           if(!mv)cf=add(cf,temp.first);
       }
   }
   else
   {
       for(int nbr=0;nbr<2;nbr++)
       {
           pair<int,int> temp=solve(depth+1,br+nbr,chk,con,s);
           way=add(way,temp.first);
           sum=add(sum,temp.second);
           if(mv!=nbr)cf=add(cf,temp.first);
       }
   }
   sum=add(sum,mul(cf,power[n-depth-2]));
   return f[depth][br][chk][con]=make_pair(way,sum);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    cin >> path;
    cin >> a;
    cin >> b;
    sett();
    a[0]=b[0]='0';
    int reza=0;
    int rezb=0;
    memset(f,-1,sizeof f);
    rezb=solve(0,0,0,1,b).second;
    rezb=add(rezb,mul(power[n-1],f[0][0][0][1].first));
    memset(f,-1,sizeof f);
    reza=solve(0,0,0,1,a).second;
    reza=add(reza,mul(power[n-1],f[0][0][0][1].first));
    int rez=add(rezb,-reza);
    a[0]='1';
    for(int i=0;i<a.size();i++)
    {
        if(a[i]=='1')rez=add(rez,power[n-i-1]);
    }
    cout << rez;
    return 0;
}

Compilation message (stderr)

ljetopica.cpp: In function 'std::pair<int, int> solve(int, int, bool, bool, const string&)':
ljetopica.cpp:32:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(depth==path.size())return make_pair(br==k,0);
       ~~~~~^~~~~~~~~~~~~
ljetopica.cpp: In function 'int main()':
ljetopica.cpp:96:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<a.size();i++)
                 ~^~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 17 / 17
• Subtask 4: 61 / 61