oj.uz

Submission #866813

# Submission time Handle Problem Language Result Execution time Memory
866813 2023-10-27T07:43:50 Z may7002 Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1354 ms 268636 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>n3)return 0;
    if(get(1,j,1,n1)!=get(2,i,1,n1))return 0;
    int n2=c[i].size()-1;
    if(n2>n3)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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5468 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 2 ms 5296 KB Output is correct
4 Correct 2 ms 5288 KB Output is correct
5 Correct 2 ms 5468 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 2 ms 5212 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 139860 KB Output is correct
2 Correct 961 ms 226980 KB Output is correct
3 Correct 560 ms 206452 KB Output is correct
4 Correct 774 ms 210328 KB Output is correct
5 Correct 703 ms 186116 KB Output is correct
6 Correct 664 ms 192092 KB Output is correct
7 Correct 479 ms 225940 KB Output is correct
8 Correct 682 ms 268636 KB Output is correct
9 Correct 634 ms 268064 KB Output is correct
10 Correct 1354 ms 212568 KB Output is correct

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 Correct 2 ms 5468 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 2 ms 5296 KB Output is correct
4 Correct 2 ms 5288 KB Output is correct
5 Correct 2 ms 5468 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 2 ms 5212 KB Output is correct
8 Correct 225 ms 139860 KB Output is correct
9 Correct 961 ms 226980 KB Output is correct
10 Correct 560 ms 206452 KB Output is correct
11 Correct 774 ms 210328 KB Output is correct
12 Correct 703 ms 186116 KB Output is correct
13 Correct 664 ms 192092 KB Output is correct
14 Correct 479 ms 225940 KB Output is correct
15 Correct 682 ms 268636 KB Output is correct
16 Correct 634 ms 268064 KB Output is correct
17 Correct 1354 ms 212568 KB Output is correct
18 Runtime error 30 ms 860 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -