oj.uz

Submission #332665

# Submission time Handle Problem Language Result Execution time Memory
332665 2020-12-03T02:33:13 Z daniel920712 Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 382 ms 27884 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[55][55];
char tt[100005];
char tt2[100005];
int sz[100005];
int main()
{
    int N,M,K,t=0,i,j,k,t2,xx,yy,ans;
    scanf("%d %d",&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=(int) strlen(tt);
            sz[i]=K;
            if(K>50) 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<=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=(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(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:93:24: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int' [-Wformat=]
   93 |             printf("%lld\n",ans);
      |                     ~~~^    ~~~
      |                        |    |
      |                        |    int
      |                        long long int
      |                     %d
selling_rna.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   20 |     scanf("%d %d",&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 4 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
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 26348 KB Output is correct
2 Correct 328 ms 27884 KB Output is correct
3 Correct 216 ms 27244 KB Output is correct
4 Correct 255 ms 27884 KB Output is correct
5 Correct 260 ms 18412 KB Output is correct
6 Correct 261 ms 18668 KB Output is correct
7 Correct 217 ms 21996 KB Output is correct
8 Correct 382 ms 25452 KB Output is correct
9 Incorrect 336 ms 25452 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 8812 KB Output is correct
2 Correct 97 ms 11244 KB Output is correct
3 Correct 74 ms 9836 KB Output is correct
4 Correct 30 ms 7532 KB Output is correct
5 Correct 78 ms 11244 KB Output is correct
6 Correct 65 ms 9964 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 122 ms 26348 KB Output is correct
9 Correct 328 ms 27884 KB Output is correct
10 Correct 216 ms 27244 KB Output is correct
11 Correct 255 ms 27884 KB Output is correct
12 Correct 260 ms 18412 KB Output is correct
13 Correct 261 ms 18668 KB Output is correct
14 Correct 217 ms 21996 KB Output is correct
15 Correct 382 ms 25452 KB Output is correct
16 Incorrect 336 ms 25452 KB Output isn't correct
17 Halted 0 ms 0 KB -