oj.uz

Submission #638518

# Submission time Handle Problem Language Result Execution time Memory
638518 2022-09-06T10:31:41 Z NintsiChkhaidze Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 701 ms 42408 KB 
#include <bits/stdc++.h>
#define ll long long
#define s second
#define pb push_back
#define f first
#define left (h<<1),l,((l+r)>>1)
#define right ((h<<1)|1),((l+r)>>1) + 1,r

#define int ll
using namespace std;
 
const int N = 5005,mod = 1000000007;
int len[N],h[N][N],p[N];

signed main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    
    int n,m;
    cin>>n>>m;

    p[0] = 1;
    for (int i = 1; i <= 5000; i++)
        p[i] = (p[i - 1]*31)%mod;

    for (int i = 1; i <= n; i++){
        string s;
        cin>>s;
        
        len[i] = s.size();
        for (int j = 0; j < len[i]; j++){
            if(j) h[i][j] = (h[i][j - 1] + (p[j]*(s[j] - 'A' + 1))%mod)%mod;
            else h[i][j] = (s[j] - 'A' + 1);
        }
    }

    while(m--){
        string a,b;
        cin>>a>>b;
        int cnt=0,A = a.size(),B = b.size(),ha = 0,hb = 0;
        for (int i = 0; i < A; i++) ha = (ha + (p[i]*(a[i] - 'A' + 1)))%mod;
        for (int i = 0; i < B; i++) hb = (hb + (p[i]*(b[i] - 'A' + 1)))%mod;
        
        for (int i = 1; i <= n; i++){
            int Ha = h[i][A - 1];
            if (Ha != ha) continue;
            int Hb = ((h[i][len[i] - 1] - h[i][len[i] - B - 1])%mod + mod)%mod;
            if (Hb == (hb*p[len[i] - B])%mod) cnt++;
        }

        cout<<cnt<<"\n";
    }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 27940 KB Output is correct
2 Correct 473 ms 40316 KB Output is correct
3 Correct 259 ms 33032 KB Output is correct
4 Correct 338 ms 40452 KB Output is correct
5 Correct 311 ms 32860 KB Output is correct
6 Correct 380 ms 32896 KB Output is correct
7 Correct 243 ms 24520 KB Output is correct
8 Correct 302 ms 42408 KB Output is correct
9 Correct 271 ms 42108 KB Output is correct
10 Correct 701 ms 39828 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 64 ms 42196 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 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 113 ms 27940 KB Output is correct
9 Correct 473 ms 40316 KB Output is correct
10 Correct 259 ms 33032 KB Output is correct
11 Correct 338 ms 40452 KB Output is correct
12 Correct 311 ms 32860 KB Output is correct
13 Correct 380 ms 32896 KB Output is correct
14 Correct 243 ms 24520 KB Output is correct
15 Correct 302 ms 42408 KB Output is correct
16 Correct 271 ms 42108 KB Output is correct
17 Correct 701 ms 39828 KB Output is correct
18 Runtime error 64 ms 42196 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -