제출 #332910

#제출 시각아이디문제언어결과실행 시간메모리
332910daniel920712Selling RNA Strands (JOI16_selling_rna)C++14
35 / 100
1566 ms379952 KiB
#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]; struct B { int l,r; int nxl,nxr; int nxt; int con; }Node2[20000005]; 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 now2=1,N; 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]]); } void New2(int l,int r,int nxt,int here) { Node2[here].l=l; Node2[here].r=r; Node2[here].nxt=nxt; Node2[here].nxl=-1; Node2[here].nxr=-1; Node2[here].con=0; } void add(int x,int y,int here) { //printf("%d %d %d %d %d %d\n",x,y,here,Node2[here].l,Node2[here].r,Node2[here].nxt); Node2[here].con++; if(Node2[here].nxt==-2) { if(y==Node2[here].l&&y==Node2[here].r) return ; if(y<=(Node2[here].l+Node2[here].r)/2) { if(Node2[here].nxl==-1) { Node2[here].nxl=now2++; New2(Node2[here].l,(Node2[here].l+Node2[here].r)/2,-2,Node2[here].nxl); } add(x,y,Node2[here].nxl); } else { if(Node2[here].nxr==-1) { Node2[here].nxr=now2++; New2((Node2[here].l+Node2[here].r)/2+1,Node2[here].r,-2,Node2[here].nxr); } add(x,y,Node2[here].nxr); } } else { if(Node2[here].nxt==-1) { Node2[here].nxt=now2++; New2(0,N,-2,Node2[here].nxt); } add(x,y,Node2[here].nxt); if(x==Node2[here].l&&x==Node2[here].r) return; if(x<=(Node2[here].l+Node2[here].r)/2) { if(Node2[here].nxl==-1) { Node2[here].nxl=now2++; New2(Node2[here].l,(Node2[here].l+Node2[here].r)/2,-1,Node2[here].nxl); } add(x,y,Node2[here].nxl); } else { if(Node2[here].nxr==-1) { Node2[here].nxr=now2++; New2((Node2[here].l+Node2[here].r)/2+1,Node2[here].r,-1,Node2[here].nxr); } add(x,y,Node2[here].nxr); } } } int main() { pair < int , int > a,b; int 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); New2(0,N,-1,0); 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; xx[0]=all[1][i]; where[i].second=Find(1,0).first; add(where[i].first,where[i].second,0); } 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); 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); 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; }

컴파일 시 표준 에러 (stderr) 메시지

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:166:55: warning: array subscript has type 'char' [-Wchar-subscripts]
  166 |         for(j=0;j<sz[i];j++) xx[0].push_back(cha[ttt[j]]);
      |                                                  ~~~~~^
selling_rna.cpp:168:63: warning: array subscript has type 'char' [-Wchar-subscripts]
  168 |         for(j=0;j<sz[i];j++) xx[1].push_back(cha[ttt[sz[i]-j-1]]);
      |                                                  ~~~~~~~~~~~~~^
selling_rna.cpp:191:53: warning: array subscript has type 'char' [-Wchar-subscripts]
  191 |         for(j=0;j<con;j++) xx[0].push_back(cha[ttt[j]]);
      |                                                ~~~~~^
selling_rna.cpp:196:59: warning: array subscript has type 'char' [-Wchar-subscripts]
  196 |         for(j=0;j<con;j++) xx[0].push_back(cha[ttt[con-j-1]]);
      |                                                ~~~~~~~~~~~^
selling_rna.cpp:152:11: warning: unused variable 'K' [-Wunused-variable]
  152 |     int M,K,t=0,i,j,k,t2,ans=0;
      |           ^
selling_rna.cpp:152:13: warning: unused variable 't' [-Wunused-variable]
  152 |     int M,K,t=0,i,j,k,t2,ans=0;
      |             ^
selling_rna.cpp:152:21: warning: unused variable 'k' [-Wunused-variable]
  152 |     int M,K,t=0,i,j,k,t2,ans=0;
      |                     ^
selling_rna.cpp:152:23: warning: unused variable 't2' [-Wunused-variable]
  152 |     int M,K,t=0,i,j,k,t2,ans=0;
      |                       ^~
selling_rna.cpp:157:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  157 |     scanf("%d %d",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~
selling_rna.cpp:163:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  163 |         scanf("%s",ttt);
      |         ~~~~~^~~~~~~~~~
selling_rna.cpp:188:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  188 |         scanf("%s",ttt);
      |         ~~~~~^~~~~~~~~~
selling_rna.cpp:193:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  193 |         scanf("%s",ttt);
      |         ~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...