Submission #846642

#	Time	Username	Problem	Language	Result	Execution time	Memory
846642		dungz	Selling RNA Strands (JOI16_selling_rna)	C++17	10 / 100	265 ms	261928 KiB

selling_rna

//dau tuyen
//dau tuyen
//dau tuyen
#pragma GCC optimize ("O2")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define task "task"
#define task "rna"
#define prll pair<ll,ll>
#define pb push_back
#define ld long double
const ll MIN=-1e18,MAX=1e18,MOD=1e9+7,nmax=1e5+5,nmax2=2e6+5,can=1400,base=31;
string a[nmax];
pair<string,string> qu[nmax];
vector<ll> hash1[nmax];
ll hash2[nmax];
ll hash3[nmax];
ll P[nmax2];
int trie[can+5][5];
int trie2[can*5+5][can+5][5];
int sl[can*5+5][can*5+5];
int id=0,id2[can*5+5];
void build(string s1,string s2)
{
    int p=0,p2=0;
    for(int i=1;i<s1.size();i++)
    {
        int ch=s1[i]-'A';
        if(!trie[p][ch]) trie[p][ch]=++id;
        p=trie[p][ch];
    }
    reverse(s2.begin(),s2.end());
    for(int i=0;i<s2.size()-1;i++)
    {
        int ch=s2[i]-'A';
        if(!trie2[p][p2][ch]) trie2[p][p2][ch]=++id2[p];
        p2=trie2[p][p2][ch];
        sl[p][p2]+=1;
    }
}
int get(string s1,string s2)
{
    int p=0,p2=0;
    for(int i=1;i<s1.size();i++)
    {
        int ch=s1[i]-'A';
        if(!trie[p][ch]) return 0;
        p=trie[p][ch];
    }
    for(int i=0;i<s2.size()-1;i++)
    {
        int ch=s2[i]-'A';
        if(!trie2[p][p2][ch]) return 0;
        p2=trie2[p][p2][ch];
    }
    return sl[p][p2];
}
ll gethash(int idx,int l,int r)
{
    return ((hash1[idx][r]-hash1[idx][l-1]*P[r-l+1])+MOD*MOD)%MOD;
}
vector<int> grt,sml;
int main(){
    
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,t;
    cin>>n>>t;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        for(auto &i:a[i])
        {
            if(i=='G') i='B';
            if(i=='U') i='D';
        }
        if(a[i].size()>can) grt.push_back(i);
        else sml.push_back(i);
    }
    for(int i=1;i<=t;i++)
    {
        cin>>qu[i].fi>>qu[i].se;
        for(auto &i:qu[i].fi)
        {
           if(i=='G') i='B';
           if(i=='U') i='D';
        }
        for(auto &i:qu[i].se)
        {
            if(i=='G') i='B';
            if(i=='U') i='D';
        }
    }
    P[0]=1;
    for(int i=1;i<=2000000;i++) P[i]=(P[i-1]*base)%MOD;
    for(int i=1;i<=n;i++)
    {
        a[i]=" "+a[i];
        hash1[i].resize(a[i].size());
        for(int j=1;j<a[i].size();j++)
        {
            hash1[i][j]=(hash1[i][j-1]*base+a[i][j]-'A'+1)%MOD;
        }
    }
    for(int i=1;i<=t;i++)
    {
        qu[i].fi=" "+qu[i].fi;
        qu[i].se=" "+qu[i].se;
        for(int j=1;j<qu[i].fi.size();j++)
        {
            hash2[i]=(hash2[i]*base+qu[i].fi[j]-'A'+1)%MOD;
        }
        for(int j=1;j<qu[i].se.size();j++)
        {
            hash3[i]=(hash3[i]*base+qu[i].se[j]-'A'+1)%MOD;
        }
    }
    for(auto i:sml)
    {
        string s=" ";
        for(int j=1;j<a[i].size();j++)
        {
            s+=a[i][j];
            build(s,a[i]);
        }
    }
    for(int i=1;i<=t;i++)
    {
        int ans=0;
        for(auto j:grt)
        {
            if(gethash(j,1,qu[i].fi.size()-1)==hash2[i] and
               gethash(j,a[j].size()-qu[i].se.size()+1,a[j].size()-1)==hash3[i])
               {
                   ans++;
               }
        }
        if(qu[i].fi.size()<can and qu[i].se.size()<can)
        {
            reverse(qu[i].se.begin(),qu[i].se.end());
            ans+=get(qu[i].fi,qu[i].se);
        }
        cout<<ans<<endl;
    }

}
/*

*/

Compilation message (stderr)

selling_rna.cpp:12: warning: "task" redefined
   12 | #define task "rna"
      | 
selling_rna.cpp:11: note: this is the location of the previous definition
   11 | #define task "task"
      | 
selling_rna.cpp: In function 'void build(std::string, std::string)':
selling_rna.cpp:30:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(int i=1;i<s1.size();i++)
      |                 ~^~~~~~~~~~
selling_rna.cpp:37:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int i=0;i<s2.size()-1;i++)
      |                 ~^~~~~~~~~~~~
selling_rna.cpp: In function 'int get(std::string, std::string)':
selling_rna.cpp:48:18: 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 i=1;i<s1.size();i++)
      |                 ~^~~~~~~~~~
selling_rna.cpp:54:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(int i=0;i<s2.size()-1;i++)
      |                 ~^~~~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:103:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |         for(int j=1;j<a[i].size();j++)
      |                     ~^~~~~~~~~~~~
selling_rna.cpp:112:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |         for(int j=1;j<qu[i].fi.size();j++)
      |                     ~^~~~~~~~~~~~~~~~
selling_rna.cpp:116:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |         for(int j=1;j<qu[i].se.size();j++)
      |                     ~^~~~~~~~~~~~~~~~
selling_rna.cpp:124:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |         for(int j=1;j<a[i].size();j++)
      |                     ~^~~~~~~~~~~~

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