Submission #343125

#	Time	Username	Problem	Language	Result	Execution time	Memory
343125		Parsa_PG	Selling RNA Strands (JOI16_selling_rna)	C++14	10 / 100	603 ms	34284 KiB

selling_rna

/* Rastegary Az Shoroe Ye EDAST */
#include <bits/stdc++.h>
     
#define pb push_back
#define endl "\n"
#define ll long long
 
using namespace std;
 
const int maxn = 5e3 + 10 , Maxn = 1e5 + 10, lg = 22 , p = 17;
const int mod = 22777;
const ll inf = 1e18 + 10;
 
int bpw[maxn] , psum[maxn][Maxn];
 
void PG(){
	bpw[0] = 1;
	for(int i = 1 ; i < maxn ; i++)
		bpw[i] = (bpw[i - 1]*p)%mod;
}
 
int check(char c){
	if(c == 'A')
		return 0;
	if(c == 'C')
		return 1;
	if(c == 'G')
		return 2;
	return 3;
}
 
int32_t main(){
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n , m;
	cin >> n >> m;
	PG();
	string s[maxn];
	for(int i = 0 ; i < n ; i ++){
		cin >> s[i];
		psum[i][0] = check(s[i][0]);
		for(int j = 1 ; j < (int)s[i].size() ; j++)
			psum[i][j] = (psum[i][j - 1] + ((check(s[i][j]) * bpw[j]) % mod))% mod;
	}
	string p , q;
	while(m--){
		cin >> p >> q;
		int ph = check(p[0]) , qh = check(q[0]);
		for(int i = 1 ; i < (int)p.size() ; i++)
			ph = (ph + (bpw[i] * check(p[i])) % mod) % mod; 
		for(int i = 1 ; i < (int)q.size() ; i++)
			qh = (qh + (bpw[i] * check(q[i])) % mod) % mod; 
		int ans = 0;
		for(int i = 0 ; i < n ; i++){
			if(s[i].size() < q.size() || s[i].size() < p.size())
				continue;
			int pref = psum[i][p.size() - 1];
			int suf = (psum[i][s[i].size() - 1] - psum[i][s[i].size() - q.size() - 1] + mod) % mod;
			if(pref == ph && ((qh * bpw[s[i].size() - q.size()] ) % mod) == suf)
				ans++;
		}
		cout << ans << endl;
	}
	return 0;
}

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