Submission #332609

#	Time	Username	Problem	Language	Result	Execution time	Memory
332609		8e7	Selling RNA Strands (JOI16_selling_rna)	C++14	35 / 100	1591 ms	38124 KiB

selling_rna

//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 (stderr)

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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40