oj.uz

Submission #866798

# Submission time Handle Problem Language Result Execution time Memory
866798 2023-10-27T07:15:23 Z harao Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 630 ms 252484 KB 
#include<bits/stdc++.h>
using namespace std;

const int N = 5e3+7;
const int M = 2e5+7;
const int base = 33;
const int mod = 1e9+7;
using ll = long long;

string s[N];
ll ha1[N][N],ha2[N][N],h[N];
int n,m;

ll get1(int i, int l, int r)
{
    return (ha1[i][r] - ha1[i][l-1]*h[r-l+1] + 1ll*mod*mod)%mod;
}

ll get2(int i, int l, int r)
{
    return (ha2[i][r] - ha2[i][l-1]*h[r-l+1] + 1ll*mod*mod)%mod;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);


    cin>>n>>m;
    int max_len = 0;
    for(int i = 1; i <= n; i++)
    {
        cin>>s[i];
        max_len = max(max_len,(int)s[i].size());
    }

    for(int i = 1; i <= n; i++)
    {
        ha1[i][0] = 0;
        string st = s[i];
        int sz = s[i].size();
        s[i] = " " + s[i];
        reverse(st.begin(),st.end());
        st = " " + st;
        for(int j = 1; j <= sz; j++)
        {
            ha1[i][j] = (ha1[i][j-1]*base + s[i][j])%mod;
            ha2[i][j] = (ha2[i][j-1]*base + st[j])%mod;
        }
    }

    h[0] = 1;
    for(int i = 1; i <= max_len; i++)
    {
        h[i] = (h[i-1]*base)%mod;
    }

    for(int i = 1; i <= m; i++)
    {
        string s1,s2;
        cin>>s1>>s2;
        int sz1 = s1.size(), sz2 = s2.size();
        reverse(s2.begin(),s2.end());
        s1 = " " + s1, s2 = " " + s2;
        ll ha1 = 0, ha2 = 0;
        for(int j = 1; j <= sz1; j++)
        {
            ha1 = (ha1*1ll*base + s1[j])%mod;
        }
        for(int j = 1; j <= sz2; j++)
        {
            ha2 = (ha2*1ll*base + s2[j])%mod;
        }

        int cnt = 0;
        for(int i1 = 1; i1 <= n; i1++)
        {
            int sz = s[i1].size() - 1;
            if(get1(i1,1,sz1) == ha1 && get2(i1,1,sz2) == ha2) cnt++;
        }
        cout<<cnt<<"\n";
    }
    return 0;
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:79:17: warning: unused variable 'sz' [-Wunused-variable]
   79 |             int sz = s[i1].size() - 1;
      |                 ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7000 KB Output is correct
2 Correct 1 ms 7004 KB Output is correct
3 Correct 1 ms 7004 KB Output is correct
4 Correct 1 ms 7004 KB Output is correct
5 Correct 1 ms 7004 KB Output is correct
6 Correct 1 ms 7004 KB Output is correct
7 Correct 1 ms 7004 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 110140 KB Output is correct
2 Correct 630 ms 245652 KB Output is correct
3 Correct 168 ms 172368 KB Output is correct
4 Correct 303 ms 252484 KB Output is correct
5 Correct 250 ms 237276 KB Output is correct
6 Correct 274 ms 240976 KB Output is correct
7 Correct 202 ms 103304 KB Output is correct
8 Correct 166 ms 248872 KB Output is correct
9 Correct 166 ms 248656 KB Output is correct
10 Correct 515 ms 247932 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 856 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 1 ms 7000 KB Output is correct
2 Correct 1 ms 7004 KB Output is correct
3 Correct 1 ms 7004 KB Output is correct
4 Correct 1 ms 7004 KB Output is correct
5 Correct 1 ms 7004 KB Output is correct
6 Correct 1 ms 7004 KB Output is correct
7 Correct 1 ms 7004 KB Output is correct
8 Correct 152 ms 110140 KB Output is correct
9 Correct 630 ms 245652 KB Output is correct
10 Correct 168 ms 172368 KB Output is correct
11 Correct 303 ms 252484 KB Output is correct
12 Correct 250 ms 237276 KB Output is correct
13 Correct 274 ms 240976 KB Output is correct
14 Correct 202 ms 103304 KB Output is correct
15 Correct 166 ms 248872 KB Output is correct
16 Correct 166 ms 248656 KB Output is correct
17 Correct 515 ms 247932 KB Output is correct
18 Runtime error 8 ms 856 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -