oj.uz

Submission #1067739

# Submission time Handle Problem Language Result Execution time Memory
1067739 2024-08-21T02:41:44 Z khactrung1912 Selling RNA Strands (JOI16_selling_rna) C++14
10 / 100
 1500 ms 1048576 KB 
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define	ins insert
#define BIT(x,i) 	((1LL<<i)&x)
#define all(x) x.begin(),x.end()
#define pll 		pair<ll,ll>
#define pii 		pair<int,int>
#define ll long long
#define ull unsigned long long
#define name "file"
const int mod=int(1e9+7);
int pi[8]={0,0,1,-1,1,1,-1,-1};
int pj[8]={-1,1,0,0,1,-1,1,-1};
template<class A,class B> inline void add(A &a,B b) { a+=b;while (a>=mod) a-=mod;}
template<class A,class B> inline void sub(A &a,B b) { a-=b;while (a>=mod) a-=mod;while (a<0) a+=mod;}
template<class A,class B> bool _max(A &a,B b) {if (a<b) return a=b,1; return 0;}
template<class A,class B> bool _min(A &a,B b) {if (a>b) return a=b,1; return 0;}
const int nmax=1e5+10;
unordered_map<int,unordered_map<int,ll>> prefix[nmax],suffix[nmax];
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    if (fopen(name".inp","r"))
        {
            freopen(name".inp","r",stdin);
            freopen(name".out","w+",stdout);
        }
    int n,m;cin>>n>>m;
    const int base0=1912;
    const int base1=2410;
    const int mod0=19122007;
    const int mod1=24102007;
    for(int i=1;i<=n;i++)
        {
            string st,a;
            cin>>st;a=st;
            st=' '+st;
            for(int j=1;j<st.size();j++) 
                {
                    prefix[i][j][0]=(1LL*prefix[i][j-1][0]*base0+(st[j]-'A'+1))%mod0;
                    prefix[i][j][1]=(1LL*prefix[i][j-1][1]*base1+(st[j]-'A'+1))%mod1;
                }
            reverse(all(a));
            a=' '+a;
            for(int j=1;j<a.size();j++){
                suffix[i][j][0]=(1LL*suffix[i][j-1][0]*base0+(a[j]-'A'+1))%mod0;
                suffix[i][j][1]=(1LL*suffix[i][j-1][1]*base1+(a[j]-'A'+1))%mod1;
            }
        }
    for(int i=1;i<=m;i++){
        string a,b;
        cin>>a>>b;
        ll P1=0,S1=0,P2=0,S2=0,cnt=0;
        for(int j=0;j<a.size();j++) 
            {
                P1=(1LL*P1*base0+(a[j]-'A'+1))%mod0;
                P2=(1LL*P2*base1+(a[j]-'A'+1))%mod1;
            }
        for(int j=b.size()-1;j>=0;j--){
            S1=(1LL*S1*base0+(b[j]-'A'+1))%mod0;
            S2=(1LL*S2*base1+(b[j]-'A'+1))%mod1;
        }
        for(int j=1;j<=n;j++)
            if (prefix[j][a.size()][0]==P1 and prefix[j][a.size()][1]==P2 and suffix[j][b.size()][0]==S1 and suffix[j][b.size()][1]==S2) cnt++;
            
        cout<<cnt<<"\n";
    }
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:41:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |             for(int j=1;j<st.size();j++)
      |                         ~^~~~~~~~~~
selling_rna.cpp:48:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |             for(int j=1;j<a.size();j++){
      |                         ~^~~~~~~~~
selling_rna.cpp:57:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for(int j=0;j<a.size();j++)
      |                     ~^~~~~~~~~
selling_rna.cpp:28:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |             freopen(name".inp","r",stdin);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:29:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |             freopen(name".out","w+",stdout);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11612 KB Output is correct
2 Correct 7 ms 11612 KB Output is correct
3 Correct 6 ms 11612 KB Output is correct
4 Correct 7 ms 11612 KB Output is correct
5 Correct 7 ms 11672 KB Output is correct
6 Correct 6 ms 11612 KB Output is correct
7 Correct 6 ms 11612 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1398 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1571 ms 97876 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11612 KB Output is correct
2 Correct 7 ms 11612 KB Output is correct
3 Correct 6 ms 11612 KB Output is correct
4 Correct 7 ms 11612 KB Output is correct
5 Correct 7 ms 11672 KB Output is correct
6 Correct 6 ms 11612 KB Output is correct
7 Correct 6 ms 11612 KB Output is correct
8 Runtime error 1398 ms 1048576 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -