Submission #933074

#	Time	Username	Problem	Language	Result	Execution time	Memory
933074		vjudge1	Selling RNA Strands (JOI16_selling_rna)	C++17	35 / 100	1555 ms	19792 KiB

selling_rna

#include <bits/stdc++.h>
#define endl '\n'
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define fore(i,l,r) for(int i = l; i < r;i++)
#define forex(i,r,l) for(int i = r; i>= l;i--)
#define fo(i,n) fore(i,0,n)
#define ffo(i,n) forex(i,n-1,0)
#define lsb(x) x&(-x)
using namespace std;
using ii = pair<int,int>;using ll = long long; using ull = unsigned long long;
using vi = vector<int>;
const int N = 1e5+7,mod=1e9+7,P=31;
ll po[N],ipo[N];
ll fpow(ll a, ll b, ll res = 1 ){
    while(b>0){
        if(b&1)res = (res * a) %mod;
        a = (a*a)%mod; b >>=1;
    }return res;
}
int to(char a){return a-'A'+1;}
struct hashing{
    vector<ll> hash1; int n;
    hashing(string &cad){n=cad.size();
        hash1.resize(n+4,0);
        // cout << n << endl;return;
        fore(i,1,n+1){
            hash1[i] = ((1ll*to(cad[i-1])*po[i])%mod + hash1[i-1])%mod;
            // cout << hash1[i] << " ";
        }
        // cout << endl;
    }
    pair<ll,ll> pre_suf(int l, int r ){
        ll num = (1ll*(hash1[n] - hash1[r-1]+mod)%mod*(ipo[r-1]))%mod;
        return mp(hash1[l],num);
    }
};
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,m; cin >> n >> m;
    po[0]=1;ipo[0]=1;
    fore(i,1,N){po[i]=(po[i-1]*P)%mod;ipo[i]=fpow(po[i],mod-2);}
    vector<hashing> arr;
    fo(i,n){
        string cad; cin >> cad;
        hashing a(cad);
        arr.pb(a);
    }
    while(m--){
        string cad1,cad2;
        cin >> cad1 >> cad2;
        // cout << cad1.size() << " " << cad2<< endl;
        hashing a(cad1),b(cad2);
        int ans = 0;
        fo(i,n){
            if(cad1.size() > arr[i].n || cad2.size() > arr[i].n) continue;
            auto act = arr[i].pre_suf(cad1.size(),arr[i].n-cad2.size()+1);
            if(act.f == a.hash1[cad1.size()] and act.s == b.hash1[cad2.size()])ans++;
        }
        cout << ans << endl;
    }
}
/*
add(--l)
add(++r)
remove(l++)
remove(r--)
*/

Compilation message (stderr)

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:59:28: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |             if(cad1.size() > arr[i].n || cad2.size() > arr[i].n) continue;
      |                ~~~~~~~~~~~~^~~~~~~~~~
selling_rna.cpp:59:54: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |             if(cad1.size() > arr[i].n || cad2.size() > arr[i].n) continue;
      |                                          ~~~~~~~~~~~~^~~~~~~~~~

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