oj.uz

Submission #332711

# Submission time Handle Problem Language Result Execution time Memory
332711 2020-12-03T03:58:06 Z daniel920712 Selling RNA Strands (JOI16_selling_rna) C++14
60 / 100
 1500 ms 140336 KB 
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <string.h>
#include <map>

using namespace std;
int MOD=1e9+7;
vector < int > a[100005],b[100005];
vector < int > can;
map < pair < int , int > , int > con[105][105];
char tt[100005];
char tt2[100005];
int sz[100005];
int big=80;
int main()
{
    int N,M,K,t=0,i,j,k,t2,xx,yy,ans;
    scanf("%d %d",&N,&M);
    for(i=0;i<N;i++)
    {
        scanf("%s",tt);
        K=(int) strlen(tt);
        sz[i]=K;
        if(K>big) can.push_back(i);
        t=0;
        for(j=0;j<K;j++)
        {
            t=(int) ( ((long long) t)*4%MOD);
            if(tt[j]=='U') t++;
            if(tt[j]=='C') t+=2;
            if(tt[j]=='G') t+=3;
            t%=MOD;
            a[i].push_back(t);
        }

        t=0;
        for(j=K-1;j>=0;j--)
        {
            t=(int) ( ((long long) t)*4%MOD);
            if(tt[j]=='U') t++;
            if(tt[j]=='C') t+=2;
            if(tt[j]=='G') t+=3;
            t%=MOD;
            b[i].push_back(t);
        }


        if(K<=big)
        {
            for(j=0;j<K;j++) for(k=0;k<K;k++) con[j][k][make_pair(a[i][j],b[i][k])]++;
            a[i].clear();
            b[i].clear();
        }
    }
    while(M--)
    {
        ans=0;
        scanf("%s %s",tt,tt2);

        xx=strlen(tt);
        yy=strlen(tt2);

        t=0;
        for(j=0;j<xx;j++)
        {
            t=(int) ( ((long long) t)*4%MOD);
            if(tt[j]=='U') t++;
            if(tt[j]=='C') t+=2;
            if(tt[j]=='G') t+=3;
            t%=MOD;
        }

        t2=0;
        for(j=yy-1;j>=0;j--)
        {
            t2=(int) (((long long) t2)*4%MOD);
            if(tt2[j]=='U') t2++;
            if(tt2[j]=='C') t2+=2;
            if(tt2[j]=='G') t2+=3;
            t2%=MOD;
        }

        for(auto i:can)
        {
            if(sz[i]<xx||sz[i]<yy) continue;
            if(a[i][xx-1]==t&&b[i][yy-1]==t2) ans++;
        }
        if(xx<=big&&yy<=big&&con[xx-1][yy-1].find(make_pair(t,t2))!=con[xx-1][yy-1].end()) ans+=con[xx-1][yy-1][make_pair(t,t2)];
        printf("%d\n",ans);


    }
    return 0;
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   21 |     scanf("%d %d",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~
selling_rna.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   24 |         scanf("%s",tt);
      |         ~~~~~^~~~~~~~~
selling_rna.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |         scanf("%s %s",tt,tt2);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 53172 KB Output is correct
2 Correct 1419 ms 116808 KB Output is correct
3 Correct 453 ms 76908 KB Output is correct
4 Correct 708 ms 116332 KB Output is correct
5 Correct 786 ms 126652 KB Output is correct
6 Correct 741 ms 122732 KB Output is correct
7 Correct 252 ms 22892 KB Output is correct
8 Correct 425 ms 25984 KB Output is correct
9 Correct 390 ms 25836 KB Output is correct
10 Correct 460 ms 25836 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 9324 KB Output is correct
2 Correct 86 ms 11628 KB Output is correct
3 Correct 70 ms 10220 KB Output is correct
4 Correct 33 ms 7916 KB Output is correct
5 Correct 78 ms 11644 KB Output is correct
6 Correct 67 ms 10348 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5612 KB Output is correct
2 Correct 5 ms 5612 KB Output is correct
3 Correct 4 ms 5612 KB Output is correct
4 Correct 5 ms 5612 KB Output is correct
5 Correct 4 ms 5612 KB Output is correct
6 Correct 5 ms 5760 KB Output is correct
7 Correct 5 ms 5612 KB Output is correct
8 Correct 332 ms 53172 KB Output is correct
9 Correct 1419 ms 116808 KB Output is correct
10 Correct 453 ms 76908 KB Output is correct
11 Correct 708 ms 116332 KB Output is correct
12 Correct 786 ms 126652 KB Output is correct
13 Correct 741 ms 122732 KB Output is correct
14 Correct 252 ms 22892 KB Output is correct
15 Correct 425 ms 25984 KB Output is correct
16 Correct 390 ms 25836 KB Output is correct
17 Correct 460 ms 25836 KB Output is correct
18 Correct 37 ms 9324 KB Output is correct
19 Correct 86 ms 11628 KB Output is correct
20 Correct 70 ms 10220 KB Output is correct
21 Correct 33 ms 7916 KB Output is correct
22 Correct 78 ms 11644 KB Output is correct
23 Correct 67 ms 10348 KB Output is correct
24 Execution timed out 1573 ms 140336 KB Time limit exceeded
25 Halted 0 ms 0 KB -