oj.uz

Submission #148071

# Submission time Handle Problem Language Result Execution time Memory
148071 2019-08-31T13:38:32 Z JovanK26 Ljetopica (COI19_ljetopica) C++14
25 / 100
 179 ms 31992 KB 
#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)
{
   return ((i%mod+j%mod)%mod);
}
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

ljetopica.cpp: In function 'std::pair<int, int> solve(int, int, bool, bool, const string&)':
ljetopica.cpp:30: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:94:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<a.size();i++)
                 ~^~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 31864 KB Output is correct
2 Correct 34 ms 31864 KB Output is correct
3 Correct 34 ms 31848 KB Output is correct
4 Correct 34 ms 31736 KB Output is correct
5 Correct 34 ms 31736 KB Output is correct
6 Correct 34 ms 31864 KB Output is correct
7 Correct 34 ms 31836 KB Output is correct
8 Correct 34 ms 31736 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 31712 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 31872 KB Output is correct
2 Correct 87 ms 31912 KB Output is correct
3 Correct 86 ms 31880 KB Output is correct
4 Correct 169 ms 31992 KB Output is correct
5 Correct 78 ms 31872 KB Output is correct
6 Correct 179 ms 31880 KB Output is correct
7 Correct 60 ms 31864 KB Output is correct
8 Correct 83 ms 31916 KB Output is correct
9 Correct 36 ms 31868 KB Output is correct
10 Correct 79 ms 31864 KB Output is correct

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 31864 KB Output is correct
2 Correct 34 ms 31864 KB Output is correct
3 Correct 34 ms 31848 KB Output is correct
4 Correct 34 ms 31736 KB Output is correct
5 Correct 34 ms 31736 KB Output is correct
6 Correct 34 ms 31864 KB Output is correct
7 Correct 34 ms 31836 KB Output is correct
8 Correct 34 ms 31736 KB Output is correct
9 Incorrect 39 ms 31712 KB Output isn't correct
10 Halted 0 ms 0 KB -