Submission #332903

#	Time	Username	Problem	Language	Result	Execution time	Memory
332903		daniel920712	Selling RNA Strands (JOI16_selling_rna)	C++14	35 / 100	1609 ms	374752 KiB

selling_rna

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <string.h>
#include <map>

using namespace std;
struct A
{
    int nxt[5];
    int con=0;
    int len;
    int l,r;
}Node[5][2000005];
vector < vector < int > > all[5];
vector < int > xx[5];
pair < int , int > where[100005];
char ttt[100005];
int sz[100005];
int cha[505];
int now[5]={1,1};
int tt[5]={0,0};

int con;
void New(int x,int y,int z)
{
    Node[x][y].con=0;
    Node[x][y].nxt[0]=-1;
    Node[x][y].nxt[1]=-1;
    Node[x][y].nxt[2]=-1;
    Node[x][y].nxt[3]=-1;
    Node[x][y].len=z;
}
void build(int x,int y,int here)
{
    if(Node[x][here].len==sz[y])
    {
        Node[x][here].con++;
        return;
    }
    if(Node[x][here].nxt[all[x][y][Node[x][here].len]]==-1)
    {
        Node[x][here].nxt[all[x][y][Node[x][here].len]]=now[x]++;
        New(x,Node[x][here].nxt[all[x][y][Node[x][here].len]],Node[x][here].len+1);
    }
    build(x,y,Node[x][here].nxt[all[x][y][Node[x][here].len]]);
}
void BFS(int x,int here)
{
    int i;
    Node[x][here].l=tt[x];
    Node[x][here].r=tt[x]+Node[x][here].con-1;
    tt[x]+=Node[x][here].con;
    for(i=0;i<4;i++)
    {
        if(Node[x][here].nxt[i]!=-1)
        {
            BFS(x,Node[x][here].nxt[i]);
            Node[x][here].r=Node[x][Node[x][here].nxt[i]].r;
        }
    }
}
pair < int , int > Find(int x,int here)
{
    if(Node[x][here].len==con) return make_pair(Node[x][here].l,Node[x][here].r);
    if(Node[x][here].nxt[xx[0][Node[x][here].len]]==-1) return make_pair(-1,-1);
    return Find(x,Node[x][here].nxt[xx[0][Node[x][here].len]]);
}

int main()
{
    pair < int , int > a,b;
    int N,M,K,t=0,i,j,k,t2,ans=0;
    cha['A']=0;
    cha['U']=1;
    cha['C']=2;
    cha['G']=3;
    scanf("%d %d",&N,&M);
    New(0,0,0);
    New(1,0,0);
    for(i=0;i<N;i++)
    {
        scanf("%s",ttt);
        sz[i]=strlen(ttt);
        xx[0].clear();
        for(j=0;j<sz[i];j++) xx[0].push_back(cha[ttt[j]]);
        xx[1].clear();
        for(j=0;j<sz[i];j++) xx[1].push_back(cha[ttt[sz[i]-j-1]]);

        all[0].push_back(xx[0]);
        all[1].push_back(xx[1]);

        build(0,i,0);
        build(1,i,0);
    }

    BFS(0,0);
    BFS(1,0);

    for(i=0;i<N;i++)
    {
        con=sz[i];

        xx[0]=all[0][i];
        where[i].first=Find(0,0).first;

        /*for(auto i:xx[0]) printf("%d ",i);
        printf("\n");*/

        xx[0]=all[1][i];
        where[i].second=Find(1,0).first;

        /*for(auto i:xx[0]) printf("%d ",i);
        printf("\n");*/

        //printf("%d %d\n",where[i].first,where[i].second);


    }

    while(M--)
    {
        scanf("%s",ttt);
        xx[0].clear();
        con=strlen(ttt);
        for(j=0;j<con;j++) xx[0].push_back(cha[ttt[j]]);
        a=Find(0,0);

        /*for(auto i:xx[0]) printf("%d ",i);
        printf("\n");*/

        scanf("%s",ttt);
        xx[0].clear();
        con=strlen(ttt);
        for(j=0;j<con;j++) xx[0].push_back(cha[ttt[con-j-1]]);
        b=Find(1,0);

        /*for(auto i:xx[0]) printf("%d ",i);
        printf("\n");

        printf("%d %d %d %d\n",a.first,a.second,b.first,b.second);*/

        if(a.first==-1||b.first==-1) printf("0\n");
        else
        {
            ans=0;
            for(i=0;i<N;i++)
            {
                if(a.first<=where[i].first&&where[i].first<=a.second)
                {
                    if(b.first<=where[i].second&&where[i].second<=b.second) ans++;
                }
            }
            printf("%d\n",ans);
        }

    }

    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:88:55: warning: array subscript has type 'char' [-Wchar-subscripts]
   88 |         for(j=0;j<sz[i];j++) xx[0].push_back(cha[ttt[j]]);
      |                                                  ~~~~~^
selling_rna.cpp:90:63: warning: array subscript has type 'char' [-Wchar-subscripts]
   90 |         for(j=0;j<sz[i];j++) xx[1].push_back(cha[ttt[sz[i]-j-1]]);
      |                                                  ~~~~~~~~~~~~~^
selling_rna.cpp:128:53: warning: array subscript has type 'char' [-Wchar-subscripts]
  128 |         for(j=0;j<con;j++) xx[0].push_back(cha[ttt[j]]);
      |                                                ~~~~~^
selling_rna.cpp:137:59: warning: array subscript has type 'char' [-Wchar-subscripts]
  137 |         for(j=0;j<con;j++) xx[0].push_back(cha[ttt[con-j-1]]);
      |                                                ~~~~~~~~~~~^
selling_rna.cpp:75:13: warning: unused variable 'K' [-Wunused-variable]
   75 |     int N,M,K,t=0,i,j,k,t2,ans=0;
      |             ^
selling_rna.cpp:75:15: warning: unused variable 't' [-Wunused-variable]
   75 |     int N,M,K,t=0,i,j,k,t2,ans=0;
      |               ^
selling_rna.cpp:75:23: warning: unused variable 'k' [-Wunused-variable]
   75 |     int N,M,K,t=0,i,j,k,t2,ans=0;
      |                       ^
selling_rna.cpp:75:25: warning: unused variable 't2' [-Wunused-variable]
   75 |     int N,M,K,t=0,i,j,k,t2,ans=0;
      |                         ^~
selling_rna.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   80 |     scanf("%d %d",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~
selling_rna.cpp:85:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   85 |         scanf("%s",ttt);
      |         ~~~~~^~~~~~~~~~
selling_rna.cpp:125:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  125 |         scanf("%s",ttt);
      |         ~~~~~^~~~~~~~~~
selling_rna.cpp:134:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  134 |         scanf("%s",ttt);
      |         ~~~~~^~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40