oj.uz

Submission #332740

# Submission time Handle Problem Language Result Execution time Memory
332740 2020-12-03T05:59:49 Z daniel920712 Selling RNA Strands (JOI16_selling_rna) C++14
0 / 100
 487 ms 1048580 KB 
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <string.h>
#include <map>

using namespace std;
struct A
{
    int x,y;
    int con=0;
    int nxt[6][6];
}Node[10000005];
int now=1,xx,yy;
char tt[100005];
char tt2[100005];
void New(int here)
{
    Node[here].con=0;
    memset(Node[here].nxt,-1,sizeof(Node[here].nxt));
}
void build(int x,int y,int here)
{
    int a,b;
    //printf("%d %d %d\n",x,y,here);
    Node[here].con++;
    Node[here].x=x;
    Node[here].y=y;

    if(x==xx&&y==xx) return;
    if(x==xx&&y==-1) return;
    if(x==-1&&y==xx) return;

    if(x!=-1)
    {
        if(tt[x]=='A') a=0;
        if(tt[x]=='U') a=1;
        if(tt[x]=='C') a=2;
        if(tt[x]=='G') a=3;
    }
    if(y!=-1)
    {
        if(tt[xx-y-1]=='A') b=0;
        if(tt[xx-y-1]=='U') b=1;
        if(tt[xx-y-1]=='C') b=2;
        if(tt[xx-y-1]=='G') b=3;
    }

    if(x==-1)
    {
        if(Node[here].nxt[5][b]==-1)
        {
            Node[here].nxt[5][b]=now++;
            New(Node[here].nxt[5][b]);
        }
        build(-1,y+1,Node[here].nxt[5][b]);
    }
    else if(y==-1)
    {
        if(Node[here].nxt[a][5]==-1)
        {
            Node[here].nxt[a][5]=now++;
            New(Node[here].nxt[a][5]);
        }
        build(x+1,-1,Node[here].nxt[a][5]);
    }
    else
    {
        if(Node[here].nxt[a][b]==-1)
        {
            Node[here].nxt[a][b]=now++;
            New(Node[here].nxt[a][b]);
        }
        //printf("%d %d %d %d\n",here,a,b,Node[here].nxt[a][b]);
        build(x+1,y+1,Node[here].nxt[a][b]);

        if(Node[here].nxt[a][5]==-1)
        {
            Node[here].nxt[a][5]=now++;
            New(Node[here].nxt[a][5]);
        }
        build(x+1,-1,Node[here].nxt[a][5]);

        if(Node[here].nxt[5][b]==-1)
        {
            Node[here].nxt[5][b]=now++;
            New(Node[here].nxt[5][b]);
        }
        build(-1,y+1,Node[here].nxt[5][b]);
    }
}
int Find(int here)
{
    int a,b;
    if((Node[here].x==xx||Node[here].x==-1)&&(Node[here].y==yy||Node[here].y==-1)) return Node[here].con;
    if(Node[here].x==-1||Node[here].x==xx)
    {
        if(tt2[Node[here].y]=='A') b=0;
        if(tt2[Node[here].y]=='U') b=1;
        if(tt2[Node[here].y]=='C') b=2;
        if(tt2[Node[here].y]=='G') b=3;

        if(Node[here].nxt[5][b]==-1) return 0;
        return Find(Node[here].nxt[5][b]);
    }

    else if(Node[here].y==-1||Node[here].y==yy)
    {
        if(tt[Node[here].x]=='A') a=0;
        if(tt[Node[here].x]=='U') a=1;
        if(tt[Node[here].x]=='C') a=2;
        if(tt[Node[here].x]=='G') a=3;

        if(Node[here].nxt[a][5]==-1) return 0;
        return Find(Node[here].nxt[a][5]);
    }
    else
    {
        if(tt2[Node[here].y]=='A') b=0;
        if(tt2[Node[here].y]=='U') b=1;
        if(tt2[Node[here].y]=='C') b=2;
        if(tt2[Node[here].y]=='G') b=3;
        if(tt[Node[here].x]=='A') a=0;
        if(tt[Node[here].x]=='U') a=1;
        if(tt[Node[here].x]=='C') a=2;
        if(tt[Node[here].x]=='G') a=3;
        //printf("%d %d\n",a,b,Node[here].nxt[a][b]);
        if(Node[here].nxt[a][b]==-1) return 0;
        return Find(Node[here].nxt[a][b]);

    }
}
int main()
{
    int N,M,K,t=0,i,j,k,t2,ans;
    scanf("%d %d",&N,&M);

    New(0);
    for(i=0;i<N;i++)
    {
        scanf("%s",tt);
        xx=strlen(tt);
        build(0,0,0);

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

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

        printf("%d\n",Find(0));
    }
    return 0;
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:137:13: warning: unused variable 'K' [-Wunused-variable]
  137 |     int N,M,K,t=0,i,j,k,t2,ans;
      |             ^
selling_rna.cpp:137:15: warning: unused variable 't' [-Wunused-variable]
  137 |     int N,M,K,t=0,i,j,k,t2,ans;
      |               ^
selling_rna.cpp:137:21: warning: unused variable 'j' [-Wunused-variable]
  137 |     int N,M,K,t=0,i,j,k,t2,ans;
      |                     ^
selling_rna.cpp:137:23: warning: unused variable 'k' [-Wunused-variable]
  137 |     int N,M,K,t=0,i,j,k,t2,ans;
      |                       ^
selling_rna.cpp:137:25: warning: unused variable 't2' [-Wunused-variable]
  137 |     int N,M,K,t=0,i,j,k,t2,ans;
      |                         ^~
selling_rna.cpp:137:28: warning: variable 'ans' set but not used [-Wunused-but-set-variable]
  137 |     int N,M,K,t=0,i,j,k,t2,ans;
      |                            ^~~
selling_rna.cpp:138:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  138 |     scanf("%d %d",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~
selling_rna.cpp:143:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  143 |         scanf("%s",tt);
      |         ~~~~~^~~~~~~~~
selling_rna.cpp:151:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  151 |         scanf("%s %s",tt,tt2);
      |         ~~~~~^~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'void build(int, int, int)':
selling_rna.cpp:53:31: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
   53 |         if(Node[here].nxt[5][b]==-1)
      |            ~~~~~~~~~~~~~~~~~~~^
selling_rna.cpp:79:31: warning: 'a' may be used uninitialized in this function [-Wmaybe-uninitialized]
   79 |         if(Node[here].nxt[a][5]==-1)
      |            ~~~~~~~~~~~~~~~~~~~^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 469 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 487 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 485 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 469 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -