oj.uz

Submission #92831

# Submission time Handle Problem Language Result Execution time Memory
92831 2019-01-05T08:53:05 Z LittleFlowers__ Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1500 ms 210680 KB 
#include <bits/stdc++.h>
using namespace std;
const int SIZE=1<<10;
int pointer = SIZE;
char buffer[SIZE];
inline char gch(){if(pointer==SIZE){fread(buffer,1,SIZE,stdin);pointer=0;}return buffer[pointer++];}
inline int in(){int x=0;char c=gch();bool neg=false;while(c!='-'&&('0'>c||c>'9')) c=gch();if(c=='-') neg=true,c=gch();while('0'<=c&&c<='9') x=10*x+c-'0',c=gch();if(neg) x=-x;return x;}
inline string sn()
{
    string s="";char c;
    while(!isupper(c=gch()));
    while(isupper(c)) s+=c,c=gch();
    return s;}
inline void out(int x){if(x>9) out(x/10);putchar(x%10+'0');}
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)
{
    s=sn();
    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;
    s=sn();
    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;
    s=sn();
    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";
    out(ans),putchar('\n');
}
int main()
{
    //freopen("RNA.inp","r",stdin);
    n=in(),m=in();
    for(int i=0; i<n; ++i) add(i);
    for(int i=0; i<m; ++i) get();
}

Compilation message

selling_rna.cpp: In function 'char gch()':
selling_rna.cpp:6:42: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 inline char gch(){if(pointer==SIZE){fread(buffer,1,SIZE,stdin);pointer=0;}return buffer[pointer++];}
                                     ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 94328 KB Output is correct
2 Correct 75 ms 94328 KB Output is correct
3 Correct 75 ms 94328 KB Output is correct
4 Correct 78 ms 94232 KB Output is correct
5 Correct 73 ms 94300 KB Output is correct
6 Correct 86 ms 94316 KB Output is correct
7 Correct 85 ms 94328 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 198228 KB Output is correct
2 Correct 341 ms 192764 KB Output is correct
3 Correct 379 ms 196532 KB Output is correct
4 Correct 410 ms 191736 KB Output is correct
5 Correct 379 ms 208916 KB Output is correct
6 Correct 374 ms 210680 KB Output is correct
7 Correct 233 ms 111248 KB Output is correct
8 Correct 436 ms 173304 KB Output is correct
9 Correct 395 ms 161144 KB Output is correct
10 Correct 367 ms 160248 KB Output is correct

Subtask #3
0 / 25.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 94328 KB Output is correct
2 Correct 75 ms 94328 KB Output is correct
3 Correct 75 ms 94328 KB Output is correct
4 Correct 78 ms 94232 KB Output is correct
5 Correct 73 ms 94300 KB Output is correct
6 Correct 86 ms 94316 KB Output is correct
7 Correct 85 ms 94328 KB Output is correct
8 Correct 397 ms 198228 KB Output is correct
9 Correct 341 ms 192764 KB Output is correct
10 Correct 379 ms 196532 KB Output is correct
11 Correct 410 ms 191736 KB Output is correct
12 Correct 379 ms 208916 KB Output is correct
13 Correct 374 ms 210680 KB Output is correct
14 Correct 233 ms 111248 KB Output is correct
15 Correct 436 ms 173304 KB Output is correct
16 Correct 395 ms 161144 KB Output is correct
17 Correct 367 ms 160248 KB Output is correct
18 Execution timed out 1584 ms 95856 KB Time limit exceeded
19 Halted 0 ms 0 KB -