Submission #343084

#	Time	Username	Problem	Language	Result	Execution time	Memory
343084		Parsa_PG	Selling RNA Strands (JOI16_selling_rna)	C++14	10 / 100	560 ms	34156 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 = 11;
const int mod = 42451;
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 < 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 < p.size() ; i++)
			ph = (ph + (bpw[i] * check(p[i])) % mod) % mod; 
		for(int i = 1 ; i < 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;
}

Compilation message (stderr)

selling_rna.cpp: In function 'int32_t main()':
selling_rna.cpp:41:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |   for(int j = 1 ; j < s[i].size() ; j++)
      |                   ~~^~~~~~~~~~~~~
selling_rna.cpp:48:21: 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 < p.size() ; i++)
      |                   ~~^~~~~~~~~~
selling_rna.cpp:50:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   for(int i = 1 ; i < q.size() ; i++)
      |                   ~~^~~~~~~~~~

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