oj.uz

답안 #332706

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
332706 2020-12-03T03:52:40 Z daniel920712 Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 151 ms 68204 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[65][65];
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);
    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])]++;
            a[i].clear();
            b[i].clear();
        }
 
 
    }
    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: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:23:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   23 |         scanf("%s",tt);
      |         ~~~~~^~~~~~~~~
selling_rna.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   62 |         scanf("%s %s",tt,tt2);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5228 KB Output is correct
2 Correct 4 ms 5228 KB Output is correct
3 Correct 4 ms 5356 KB Output is correct
4 Correct 4 ms 5228 KB Output is correct
5 Correct 4 ms 5228 KB Output is correct
6 Correct 5 ms 5228 KB Output is correct
7 Correct 5 ms 5228 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 151 ms 68204 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 8844 KB Output is correct
2 Correct 84 ms 11372 KB Output is correct
3 Correct 72 ms 9964 KB Output is correct
4 Correct 38 ms 7660 KB Output is correct
5 Correct 77 ms 11244 KB Output is correct
6 Correct 65 ms 9964 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5228 KB Output is correct
2 Correct 4 ms 5228 KB Output is correct
3 Correct 4 ms 5356 KB Output is correct
4 Correct 4 ms 5228 KB Output is correct
5 Correct 4 ms 5228 KB Output is correct
6 Correct 5 ms 5228 KB Output is correct
7 Correct 5 ms 5228 KB Output is correct
8 Runtime error 151 ms 68204 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -