oj.uz

Submission #92824

# Submission time Handle Problem Language Result Execution time Memory
92824 2019-01-05T08:38:13 Z LittleFlowers__ Selling RNA Strands (JOI16_selling_rna) C++14
10 / 100
 1500 ms 210552 KB 
#include <bits/stdc++.h>
using namespace std;
const int N=2000010;
int n,m,G,Il,Ir;
int Tl[N][4],Tr[N][4];
vector<int> Fl[N],Fr[N];
string s;
void add(int i)
{
    cin>>s;
    for(auto & c : s)
    {
        if(c=='G') c='B';
        if(c=='U') c='D';
    }
    G=0;
    for(auto & c : s)
    {
        if(!Tl[G][c-'A']) Tl[G][c-'A']=++Il;
        G=Tl[G][c-'A'];
        Fl[G].push_back(i);
    }
    reverse(s.begin(),s.end());
    G=0;
    for(auto & c : s)
    {
        if(!Tr[G][c-'A']) Tr[G][c-'A']=++Ir;
        G=Tr[G][c-'A'];
        Fr[G].push_back(i);
    }
}
void get()
{
    vector<int> A;
    G=0;
    cin>>s;
    for(auto & c : s)
    {
        if(c=='G') c='B';
        if(c=='U') c='D';
    }
    for(auto & c : s)
    {
        G=Tl[G][c-'A'];
        if(!G) break;
    }
    A.insert(A.end(),Fl[G].begin(),Fl[G].end());
    G=0;
    cin>>s;
    for(auto & c : s)
    {
        if(c=='G') c='B';
        if(c=='U') c='D';
    }
    reverse(s.begin(),s.end());
    for(auto & c : s)
    {
        G=Tr[G][c-'A'];
        if(!G) break;
    }
    A.insert(A.end(),Fr[G].begin(),Fr[G].end());
    sort(A.begin(),A.end());
    int ans=0;
    for(int i=0; i<(int)A.size()-1; ++i) ans+=A[i]==A[i+1];
    cout<<ans<<"\n";
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen("RNA.inp","r",stdin);
    cin>>n>>m;
    for(int i=0; i<n; ++i) add(i);
    for(int i=0; i<m; ++i) get();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 94332 KB Output is correct
2 Correct 87 ms 94328 KB Output is correct
3 Correct 86 ms 94328 KB Output is correct
4 Correct 85 ms 94328 KB Output is correct
5 Correct 88 ms 94328 KB Output is correct
6 Correct 87 ms 94328 KB Output is correct
7 Correct 85 ms 94328 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 428 ms 198732 KB Output is correct
2 Correct 693 ms 192988 KB Output is correct
3 Correct 672 ms 196856 KB Output is correct
4 Correct 746 ms 192068 KB Output is correct
5 Correct 349 ms 208920 KB Output is correct
6 Correct 386 ms 210552 KB Output is correct
7 Correct 685 ms 111324 KB Output is correct
8 Correct 399 ms 173176 KB Output is correct
9 Correct 431 ms 161272 KB Output is correct
10 Execution timed out 1592 ms 160376 KB Time limit exceeded

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1593 ms 95592 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 94332 KB Output is correct
2 Correct 87 ms 94328 KB Output is correct
3 Correct 86 ms 94328 KB Output is correct
4 Correct 85 ms 94328 KB Output is correct
5 Correct 88 ms 94328 KB Output is correct
6 Correct 87 ms 94328 KB Output is correct
7 Correct 85 ms 94328 KB Output is correct
8 Correct 428 ms 198732 KB Output is correct
9 Correct 693 ms 192988 KB Output is correct
10 Correct 672 ms 196856 KB Output is correct
11 Correct 746 ms 192068 KB Output is correct
12 Correct 349 ms 208920 KB Output is correct
13 Correct 386 ms 210552 KB Output is correct
14 Correct 685 ms 111324 KB Output is correct
15 Correct 399 ms 173176 KB Output is correct
16 Correct 431 ms 161272 KB Output is correct
17 Execution timed out 1592 ms 160376 KB Time limit exceeded