제출 #1282814

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1282814		Faisal_Saqib	Selling RNA Strands (JOI16_selling_rna)	C++20	35 / 100	1619 ms	566888 KiB

selling_rna

#include <bits/stdc++.h>
// #include <bits/extc++.h>
// #include <ext/pb_ds/hash_policy.hpp>
// #include <ext/pb_ds/>

using namespace std;
// using namespace __gnu_pbds;
#define ll long long
const int N=2e6+10,mod=1e9+7,base=26;
string s[N],p[N],q[N];
ll pw[N],inv[N];
char cur[]={'A','A','C','G','U'};
vector<ll> pre[N];
vector<int> qos[N];
ll gethash(int i,int l,int r) // 1-base and inc inc
{
    ll k1=(pre[i][r]-pre[i][l-1]+mod)%mod;
    // pre[r] has power (r-1) we need its power to be r-l
    // pre[l] has power l-1 we need its power to be l-1
    // so mul by inverse of 
    return (k1*inv[l-1])%mod;
}
int powmod(int a,int b)
{
    int ans=1;
    while(b)
    {
        if(b&1)
            ans=(1ll*ans*a)%mod;
        a=(1ll*a*a)%mod;
        b>>=1;
    }
    return ans;
}
int main()
{
 ios::sync_with_stdio(0);
 cout.tie(0);
 cin.tie(0);
 pw[0]=1;
 for(int i=1;i<N;i++)
 {
    pw[i]=(1ll*pw[i-1]*base)%mod;
 }
 inv[N-1]=powmod(pw[N-1],mod-2);
 for(int i=N-2;i>=0;i--)
 {
    inv[i]=(1ll*inv[i+1]*base)%mod;
 }
 int n,m;
 cin>>n>>m;
 for(int i=0;i<n;i++)
 {
    cin>>s[i];
    int sz=s[i].size();
    pre[i].resize(sz+1);
    for(int j=0;j<sz;j++)
    {
        for(int p=1;p<=4;p++)
        {
            if(s[i][j]==cur[p])
            {
                pre[i][j+1]=(1ll*pre[i][j]+1ll*p*pw[j])%mod;
            }
        }
    }
}
vector<int> pos;
ll lm=1e8;
for(int i=0;i<m;i++)
{
    cin>>p[i]>>q[i];
    // if((1ll*n*m)<=lm)
    // {
    //     int hash=0;
    //     for(int j=0;j<p[i].size();j++)
    //     {
    //         for(int k=1;k<=4;k++)
    //         {
    //             if(p[i][j]==cur[k])
    //             {
    //                 hash=(1ll*hash+1ll*k*pw[j])%mod;
    //             }
    //         }
    //     }
    //     int hash1=0;
    //     for(int j=0;j<q[i].size();j++)
    //     {
    //         for(int k=1;k<=4;k++)
    //         {
    //             if(q[i][j]==cur[k])
    //             {
    //                 hash1=(1ll*hash1+1ll*k*pw[j])%mod;
    //             }
    //         }
    //     }
    //     int ans=0;
    //     for(int j=0;j<n;j++)
    //     {
    //         if(p[i].size()>s[j].size() or q[i].size()>s[j].size())continue;
    //         if(gethash(j,1,p[i].size())==hash and gethash(j,s[j].size()-q[i].size()+1,s[j].size())==hash1)
    //         {
    //             ans++;
    //         }
    //     }
    //     cout<<ans<<endl;
    //     continue;
    // }
    pos.push_back(p[i].size());
    qos[p[i].size()].push_back(q[i].size());
}
if(pos.size()==0)return 0;
sort(begin(pos),end(pos));
pos.resize(unique(begin(pos),end(pos))-begin(pos));
for(int l=1;l<N;l++)
{
    if(qos[l].size()==0)continue;
    sort(begin(qos[l]),end(qos[l]));
    qos[l].resize(unique(begin(qos[l]),end(qos[l]))-begin(qos[l]));
}

// gp_hash_table<ll,int> cnt;
map<ll,int> cnt;
// ll st=4e18;
// cout<<st<<endl;
for(int i=0;i<n;i++)
{
    // check prefix only for length in pos, and suffix for length in q
    int sz=s[i].size();
    for(auto&l:pos)
    {
        if(l>sz)break;
        int h1=gethash(i,1,l);
        for(auto&l1:qos[l])
        {
            if(l1>sz)break;
            int h2=gethash(i,sz-l1+1,sz);
            cnt[(1ll*h1*mod)+h2]++;
        }
    }
}
for(int i=0;i<m;i++)
{
    int hash=0;
    for(int j=0;j<p[i].size();j++)
    {
        for(int k=1;k<=4;k++)
        {
            if(p[i][j]==cur[k])
            {
                hash=(1ll*hash+1ll*k*pw[j])%mod;
            }
        }
    }
    int hash1=0;
    for(int j=0;j<q[i].size();j++)
    {
        for(int k=1;k<=4;k++)
        {
            if(q[i][j]==cur[k])
            {
                hash1=(1ll*hash1+1ll*k*pw[j])%mod;
            }
        }
    }
    // cout<<hash<<' '<<hash1<<endl;
    cout<<cnt[(1ll*hash*mod)+hash1]<<'\n';
}
 // A C G U 
 // 0 1 2 3
}

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