oj.uz

Submission #332666

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

using namespace std;
long long MOD=1e9+7;
vector < long long > a[100005],b[100005];
vector < long long > can;
map < pair < long long , long long > , long long > con[55][55];
char tt[100005];
char tt2[100005];
long long sz[100005];
int main()
{
    long long N,M,K,t=0,i,j,k,t2,xx,yy,ans;
    scanf("%lld %lld",&N,&M);

    if(N<=5000&&M<=5000)
    {

        for(i=0;i<N;i++)
        {
            scanf("%s",tt);
            K=(long long) strlen(tt);
            sz[i]=K;
            t=0;
            for(j=0;j<K;j++)
            {
                t*=4;
                if(tt[j]=='U') t++;
                if(tt[j]=='C') t+=2;
                if(tt[j]=='G') t+=3;
                t%=MOD;
                //printf("%lld ",t);
                a[i].push_back(t);
            }
            //printf("\n");

            t=0;
            for(j=K-1;j>=0;j--)
            {
                t*=4;
                if(tt[j]=='U') t++;
                if(tt[j]=='C') t+=2;
                if(tt[j]=='G') t+=3;
                t%=MOD;
                //printf("%lld ",t);
                b[i].push_back(t);
            }
            //printf("\n\n");
        }
        while(M--)
        {
            ans=0;
            scanf("%s %s",tt,tt2);

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

            t=0;
            for(j=0;j<xx;j++)
            {
                t*=4;
                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*=4;
                if(tt2[j]=='U') t2++;
                if(tt2[j]=='C') t2+=2;
                if(tt2[j]=='G') t2+=3;
                t2%=MOD;
            }

            //printf("%lld %lld\n",t,t2);


            for(i=0;i<N;i++)
            {
                if(sz[i]<xx||sz[i]<yy) continue;

                if(a[i][xx-1]==t&&b[i][yy-1]==t2) ans++;
            }
            printf("%lld\n",ans);


        }
    }
    else
    {

        for(i=0;i<N;i++)
        {
            scanf("%s",tt);
            K=(long long) strlen(tt);
            sz[i]=K;
            if(K>50) can.push_back(i);
            t=0;
            for(j=0;j<K;j++)
            {
                t=(long long) ( ((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=(long long) ( ((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<=50) for(j=0;j<K;j++) for(k=0;k<K;k++) con[j][k][make_pair(a[i][j],b[i][k])]++;


        }
        while(M--)
        {
            ans=0;
            scanf("%s %s",tt,tt2);

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

            t=0;
            for(j=0;j<xx;j++)
            {
                t=(long long) ( ((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=(long long) (((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(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("%lld\n",ans);


        }
    }
    return 0;
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   20 |     scanf("%lld %lld",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
selling_rna.cpp:27:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   27 |             scanf("%s",tt);
      |             ~~~~~^~~~~~~~~
selling_rna.cpp:59:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   59 |             scanf("%s %s",tt,tt2);
      |             ~~~~~^~~~~~~~~~~~~~~~
selling_rna.cpp:103:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  103 |             scanf("%s",tt);
      |             ~~~~~^~~~~~~~~
selling_rna.cpp:137:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  137 |             scanf("%s %s",tt,tt2);
      |             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 44396 KB Output is correct
2 Correct 391 ms 48492 KB Output is correct
3 Correct 248 ms 46444 KB Output is correct
4 Correct 311 ms 48492 KB Output is correct
5 Correct 351 ms 31724 KB Output is correct
6 Correct 353 ms 32108 KB Output is correct
7 Correct 239 ms 36844 KB Output is correct
8 Correct 412 ms 45548 KB Output is correct
9 Correct 354 ms 45548 KB Output is correct
10 Correct 675 ms 45548 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 9068 KB Output is correct
2 Correct 84 ms 12268 KB Output is correct
3 Correct 71 ms 10732 KB Output is correct
4 Correct 32 ms 8684 KB Output is correct
5 Correct 79 ms 12140 KB Output is correct
6 Correct 66 ms 10860 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5228 KB Output is correct
2 Correct 4 ms 5228 KB Output is correct
3 Correct 4 ms 5228 KB Output is correct
4 Correct 4 ms 5228 KB Output is correct
5 Correct 4 ms 5228 KB Output is correct
6 Correct 4 ms 5228 KB Output is correct
7 Correct 4 ms 5228 KB Output is correct
8 Correct 138 ms 44396 KB Output is correct
9 Correct 391 ms 48492 KB Output is correct
10 Correct 248 ms 46444 KB Output is correct
11 Correct 311 ms 48492 KB Output is correct
12 Correct 351 ms 31724 KB Output is correct
13 Correct 353 ms 32108 KB Output is correct
14 Correct 239 ms 36844 KB Output is correct
15 Correct 412 ms 45548 KB Output is correct
16 Correct 354 ms 45548 KB Output is correct
17 Correct 675 ms 45548 KB Output is correct
18 Correct 36 ms 9068 KB Output is correct
19 Correct 84 ms 12268 KB Output is correct
20 Correct 71 ms 10732 KB Output is correct
21 Correct 32 ms 8684 KB Output is correct
22 Correct 79 ms 12140 KB Output is correct
23 Correct 66 ms 10860 KB Output is correct
24 Runtime error 871 ms 208620 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Halted 0 ms 0 KB -