oj.uz

Submission #343084

# Submission time Handle Problem Language Result Execution time Memory
343084 2021-01-03T12:06:43 Z Parsa_PG Selling RNA Strands (JOI16_selling_rna) C++14
10 / 100
 560 ms 34156 KB 
/* 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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1004 KB Output is correct
2 Correct 1 ms 1004 KB Output is correct
3 Correct 1 ms 1004 KB Output is correct
4 Correct 1 ms 1004 KB Output is correct
5 Correct 1 ms 1004 KB Output is correct
6 Correct 1 ms 1004 KB Output is correct
7 Correct 1 ms 1004 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 19948 KB Output is correct
2 Correct 560 ms 34156 KB Output is correct
3 Correct 239 ms 25708 KB Output is correct
4 Correct 326 ms 34156 KB Output is correct
5 Incorrect 412 ms 30572 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 70 ms 30544 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1004 KB Output is correct
2 Correct 1 ms 1004 KB Output is correct
3 Correct 1 ms 1004 KB Output is correct
4 Correct 1 ms 1004 KB Output is correct
5 Correct 1 ms 1004 KB Output is correct
6 Correct 1 ms 1004 KB Output is correct
7 Correct 1 ms 1004 KB Output is correct
8 Correct 114 ms 19948 KB Output is correct
9 Correct 560 ms 34156 KB Output is correct
10 Correct 239 ms 25708 KB Output is correct
11 Correct 326 ms 34156 KB Output is correct
12 Incorrect 412 ms 30572 KB Output isn't correct
13 Halted 0 ms 0 KB -