oj.uz

Submission #332609

# Submission time Handle Problem Language Result Execution time Memory
332609 2020-12-03T01:28:45 Z 8e7 Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1500 ms 38124 KB 
//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <stack>
#define ll long long
#define maxn 100005
#define mod 1000000007
#define pri 7
#define zckorz ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
int n, m;
vector<vector<ll> > pref, suf;
vector<int> siz;
int main() {
	zckorz
	cin >> n >> m;
	for (int i = 0;i < n;i++) {
		string se;
		cin >> se;
		siz.push_back(se.size());
		vector<int> s;
		for (int j = 0;j < se.size();j++) s.push_back(se[j] == 'A' ? 1 : (se[j] == 'G' ? 2 : (se[j] == 'C' ? 3 : 4)));
		ll cur = 0;
		vector<ll> add, add2;
		for (int j = 0;j < s.size();j++) {
			cur = (cur * pri + s[j]) % mod;
			//cout << cur << " ";
			add.push_back(cur);
		}
		//cout << endl;
		cur = 0;
		for (int j = s.size() - 1;j >= 0;j--) {
			cur = (cur * pri + s[j]) % mod;
			add2.push_back(cur);
		}
		pref.push_back(add);
		suf.push_back(add2);
	}
	for (int i = 0;i < m;i++) {
		string pe, qe;
		cin >> pe >> qe;
		vector<int> p, q;
		for (int j = 0;j < pe.size();j++) p.push_back(pe[j] == 'A' ? 1 : (pe[j] == 'G' ? 2 : (pe[j] == 'C' ? 3 : 4)));
		for (int j = 0;j < qe.size();j++) q.push_back(qe[j] == 'A' ? 1 : (qe[j] == 'G' ? 2 : (qe[j] == 'C' ? 3 : 4)));
		int ans = 0;
		ll hashp = 0, hashq = 0;
		for (int j = 0;j < p.size();j++) hashp = (hashp * pri + p[j]) % mod;
		for (int j = q.size() - 1;j >= 0;j--) hashq = (hashq * pri + q[j]) % mod;
		//cout << hashp << " " << hashq << endl;
		for (int j = 0;j < n;j++) {
			if (p.size() <= siz[j] && q.size() <= siz[j]) {
				if (hashp == pref[j][p.size() - 1] && hashq == suf[j][q.size() - 1]) ans++;
			}
		}
		cout << ans << "\n";
	}
}
/*
2 3
AUGC
AGC
G C
AU C
A C
 */

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:24:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |   for (int j = 0;j < se.size();j++) s.push_back(se[j] == 'A' ? 1 : (se[j] == 'G' ? 2 : (se[j] == 'C' ? 3 : 4)));
      |                  ~~^~~~~~~~~~~
selling_rna.cpp:27:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   for (int j = 0;j < s.size();j++) {
      |                  ~~^~~~~~~~~~
selling_rna.cpp:45:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   for (int j = 0;j < pe.size();j++) p.push_back(pe[j] == 'A' ? 1 : (pe[j] == 'G' ? 2 : (pe[j] == 'C' ? 3 : 4)));
      |                  ~~^~~~~~~~~~~
selling_rna.cpp:46:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |   for (int j = 0;j < qe.size();j++) q.push_back(qe[j] == 'A' ? 1 : (qe[j] == 'G' ? 2 : (qe[j] == 'C' ? 3 : 4)));
      |                  ~~^~~~~~~~~~~
selling_rna.cpp:49:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for (int j = 0;j < p.size();j++) hashp = (hashp * pri + p[j]) % mod;
      |                  ~~^~~~~~~~~~
selling_rna.cpp:53:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
   53 |    if (p.size() <= siz[j] && q.size() <= siz[j]) {
selling_rna.cpp:53:39: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
   53 |    if (p.size() <= siz[j] && q.size() <= siz[j]) {

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 31852 KB Output is correct
2 Correct 356 ms 32236 KB Output is correct
3 Correct 233 ms 32108 KB Output is correct
4 Correct 285 ms 32128 KB Output is correct
5 Correct 309 ms 20332 KB Output is correct
6 Correct 329 ms 20716 KB Output is correct
7 Correct 229 ms 28012 KB Output is correct
8 Correct 384 ms 32236 KB Output is correct
9 Correct 350 ms 38124 KB Output is correct
10 Correct 552 ms 35820 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1591 ms 6100 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 143 ms 31852 KB Output is correct
9 Correct 356 ms 32236 KB Output is correct
10 Correct 233 ms 32108 KB Output is correct
11 Correct 285 ms 32128 KB Output is correct
12 Correct 309 ms 20332 KB Output is correct
13 Correct 329 ms 20716 KB Output is correct
14 Correct 229 ms 28012 KB Output is correct
15 Correct 384 ms 32236 KB Output is correct
16 Correct 350 ms 38124 KB Output is correct
17 Correct 552 ms 35820 KB Output is correct
18 Execution timed out 1591 ms 6100 KB Time limit exceeded
19 Halted 0 ms 0 KB -