Submission #597917

#	Time	Username	Problem	Language	Result	Execution time	Memory
597917		CSQ31	Selling RNA Strands (JOI16_selling_rna)	C++17	10 / 100	1575 ms	34008 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef pair<int,int> pii;
const int MOD1 = 1e9+7;
int MOD2;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
pii make_hash(string s){
	int n = s.size();
	int z1 = 5;
	int z2 = 5;
	pii hb;
	for(int i=0;i<n;i++){
		int c = 1;
		if(s[i] == 'C')c=2;
		else if(s[i] == 'G')c=3;
		else if(s[i] == 'U')c=4;
		hb.fi += c * 1LL * z1%MOD1;
		hb.se += c * 1LL * z2%MOD2;
		if(hb.fi>=MOD1)hb.fi-=MOD1;
		if(hb.se>=MOD2)hb.fi-=MOD1;
		
		z1 = z1 * 1LL * 7 %MOD1;
		z2 = z2 * 1LL * 7 %MOD2;
	}
	return hb;
	
	
}
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n,m;
	cin>>n>>m;
	MOD2 = uniform_int_distribution<int>(1e8,1e9)(rng);
	vector<string>s(n);
	for(int i=0;i<n;i++)cin>>s[i];
	vector<vector<pii>>ph(n),sh(n); //prefix and suffix hash
	for(int i=0;i<n;i++){
		int k = s[i].size();
		ph[i].resize(k);
		sh[i].resize(k);
		int z1 = 5;
		int z2 = 5;
		pii hb;
		for(int j=0;j<k;j++){
			int c = 1;
			if(s[i][j] == 'C')c=2;
			else if(s[i][j] == 'G')c=3;
			else if(s[i][j] == 'U')c=4;
			hb.fi += c * 1LL * z1%MOD1;
			hb.se += c * 1LL * z2%MOD2;
			if(hb.fi>=MOD1)hb.fi-=MOD1;
			if(hb.se>=MOD2)hb.se-=MOD2;
			
			z1 = z1 * 1LL * 7 %MOD1;
			z2 = z2 * 1LL * 7 %MOD2;
			ph[i][j] =hb;
		}
		z1 = 5;
		z2 = 5;
		hb = {0,0};
		reverse(s[i].begin(),s[i].end());
		for(int j=0;j<k;j++){
			int c = 1;
			if(s[i][j] == 'C')c=2;
			else if(s[i][j] == 'G')c=3;
			else if(s[i][j] == 'U')c=4;
			hb.fi += c * 1LL * z1%MOD1;
			hb.se += c * 1LL * z2%MOD2;
			if(hb.fi>=MOD1)hb.fi-=MOD1;
			if(hb.se>=MOD2)hb.se-=MOD2;
			
			z1 = z1 * 1LL * 7 %MOD1;
			z2 = z2 * 1LL * 7 %MOD2;
			sh[i][j]=hb;
		}
	}
	while(m--){
		
		string p,q;
		cin>>p>>q;
		reverse(q.begin(),q.end());
		pii pre = make_hash(p);
		pii suf = make_hash(q);
		int ans = 0;
		int a = p.size();
		int b = q.size();
		for(int i=0;i<n;i++){
			if(s[i].length() >= max(a,b)){
				if(ph[i][a-1] == pre && sh[i][b-1] == suf)ans++; 
				
			}
		}
		cout<<ans<<'\n';
		
	}
	
	
}

Compilation message (stderr)

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:91:21: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
   91 |    if(s[i].length() >= max(a,b)){
      |       ~~~~~~~~~~~~~~^~~~~~~~~~~

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