oj.uz

Submission #866807

# Submission time Handle Problem Language Result Execution time Memory
866807 2023-10-27T07:32:24 Z may7002 Selling RNA Strands (JOI16_selling_rna) C++17
0 / 100
 960 ms 224348 KB 
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=5e3+7;
string a[N],b[N],c[N];
const int mod=1e9+7;
long long bas[N],hasa[4][N][N],hasb[4][N][N];
const int base=31;
int s=0;
long long get(int id,int vt,int l,int r)
{
    return ((hasa[id][vt][r]-hasa[id][vt][l-1]*bas[r-l+1]%mod)+1ll*mod*mod)%mod;
}
long long get1(int id,int vt,int l,int r)
{
    return ((hasb[id][vt][l]-hasa[id][vt][r+1]*bas[r-l+1]%mod)+1ll*mod*mod)%mod;
}
bool check(int i,int j)
{
    int n1=b[i].size()-1;
    int n3=a[j].size()-1;
    if(n1>a[j].size())return 0;
    if(get(1,j,1,n1)!=get(2,i,1,n1))return 0;
    int n2=c[i].size()-1;
    if(n2>a[j].size())return 0;
    if(get1(1,j,n3-n2+1,n3)!=get1(3,i,1,n2))return 0;
    return 1;
}
void sol1()
{
    bas[0]=1;
    for(int i=1;i<=s;i++)bas[i]=(bas[i-1]*base)%mod;
    for(int i=1;i<=n;i++)
    {
        int si=a[i].size();
        a[i]=" "+a[i];
        for(int j=1;j<=si;j++)
        {
            hasa[1][i][j]=(hasa[1][i][j-1]*base+a[i][j]-'A')%mod;
        }
        for(int j=si;j>=1;j--)
        {
            hasb[1][i][j]=(hasb[1][i][j+1]*base+a[i][j]-'A')%mod;
        }
    }
    for(int i=1;i<=m;i++)
    {
        int si=b[i].size();
        b[i]=" "+b[i];
        for(int j=1;j<=si;j++)
        {
            hasa[2][i][j]=(hasa[2][i][j-1]*base+b[i][j]-'A')%mod;
        }
        for(int j=si;j>=1;j--)
        {
            hasb[2][i][j]=(hasb[2][i][j+1]*base+b[i][j]-'A')%mod;
        }
    }
    for(int i=1;i<=m;i++)
    {
        int si=c[i].size();
        c[i]=" "+c[i];
        for(int j=1;j<=si;j++)
        {
            hasa[3][i][j]=(hasa[3][i][j-1]*base+c[i][j]-'A')%mod;
        }
        for(int j=si;j>=1;j--)
        {
            hasb[3][i][j]=(hasb[3][i][j+1]*base+c[i][j]-'A')%mod;
        }
    }
    for(int i=1;i<=m;i++)
    {
        int sl=0;
        for(int j=1;j<=n;j++)
        {
            if(check(i,j))sl++;
        }
        cout<<sl<<'\n';
    }
}
int main ()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
//    freopen("RNA.inp","r",stdin);
//    freopen("RNA.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            int x=a[i].size();
            s=max(s,x);
        }
    for(int i=1;i<=m;i++)
        {
            cin>>b[i]>>c[i];
            int x=b[i].size();
            int y=c[i].size();
            s=max(s,max(x,y));
        }
    sol1();
    return 0;
}
//3 3
//AA
//AA
//AGA
//AA AA
//AG GA
//AG GA

Compilation message

selling_rna.cpp: In function 'bool check(int, int)':
selling_rna.cpp:22:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     if(n1>a[j].size())return 0;
      |        ~~^~~~~~~~~~~~
selling_rna.cpp:25:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     if(n2>a[j].size())return 0;
      |        ~~^~~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 137544 KB Output is correct
2 Correct 960 ms 224348 KB Output is correct
3 Correct 525 ms 203860 KB Output is correct
4 Correct 766 ms 207952 KB Output is correct
5 Incorrect 814 ms 184396 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 30 ms 860 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

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