Submission #332666

#	Time	Username	Problem	Language	Result	Execution time	Memory
332666		daniel920712	Selling RNA Strands (JOI16_selling_rna)	C++14	60 / 100	871 ms	208620 KiB

selling_rna

#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 (stderr)

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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 0 / 40