oj.uz

Submission #343092

# Submission time Handle Problem Language Result Execution time Memory
343092 2021-01-03T12:12:32 Z Parsa_PG Selling RNA Strands (JOI16_selling_rna) C++14
10 / 100
 590 ms 34284 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 = 3989;
const int mod = 23173;
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 119 ms 19948 KB Output is correct
2 Correct 590 ms 34284 KB Output is correct
3 Correct 243 ms 25708 KB Output is correct
4 Correct 330 ms 34284 KB Output is correct
5 Correct 410 ms 30316 KB Output is correct
6 Incorrect 413 ms 30828 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 62 ms 30572 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 119 ms 19948 KB Output is correct
9 Correct 590 ms 34284 KB Output is correct
10 Correct 243 ms 25708 KB Output is correct
11 Correct 330 ms 34284 KB Output is correct
12 Correct 410 ms 30316 KB Output is correct
13 Incorrect 413 ms 30828 KB Output isn't correct
14 Halted 0 ms 0 KB -