oj.uz

답안 #92826

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
92826 2019-01-05T08:43:31 Z LittleFlowers__ Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1500 ms 210624 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];
int C[N];
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()
{
    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;
    }
    int GG=G;
    for(auto & i : Fl[G]) C[i]++;
    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;
    }
    int ans=0;
    for(auto & i : Fr[G]) ans+=C[i];
    for(auto & i : Fl[GG]) C[i]=0;
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 94328 KB Output is correct
2 Correct 89 ms 94332 KB Output is correct
3 Correct 87 ms 94328 KB Output is correct
4 Correct 87 ms 94328 KB Output is correct
5 Correct 89 ms 94328 KB Output is correct
6 Correct 90 ms 94328 KB Output is correct
7 Correct 89 ms 94304 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 360 ms 198104 KB Output is correct
2 Correct 379 ms 192540 KB Output is correct
3 Correct 368 ms 196472 KB Output is correct
4 Correct 373 ms 191744 KB Output is correct
5 Correct 410 ms 208888 KB Output is correct
6 Correct 360 ms 210624 KB Output is correct
7 Correct 192 ms 111224 KB Output is correct
8 Correct 357 ms 173180 KB Output is correct
9 Correct 311 ms 161272 KB Output is correct
10 Correct 309 ms 160760 KB Output is correct

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1570 ms 96100 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 94328 KB Output is correct
2 Correct 89 ms 94332 KB Output is correct
3 Correct 87 ms 94328 KB Output is correct
4 Correct 87 ms 94328 KB Output is correct
5 Correct 89 ms 94328 KB Output is correct
6 Correct 90 ms 94328 KB Output is correct
7 Correct 89 ms 94304 KB Output is correct
8 Correct 360 ms 198104 KB Output is correct
9 Correct 379 ms 192540 KB Output is correct
10 Correct 368 ms 196472 KB Output is correct
11 Correct 373 ms 191744 KB Output is correct
12 Correct 410 ms 208888 KB Output is correct
13 Correct 360 ms 210624 KB Output is correct
14 Correct 192 ms 111224 KB Output is correct
15 Correct 357 ms 173180 KB Output is correct
16 Correct 311 ms 161272 KB Output is correct
17 Correct 309 ms 160760 KB Output is correct
18 Execution timed out 1570 ms 96100 KB Time limit exceeded
19 Halted 0 ms 0 KB -