Submission #914302

#	Time	Username	Problem	Language	Result	Execution time	Memory
914302		OAleksa	Selling RNA Strands (JOI16_selling_rna)	C++14	35 / 100	1557 ms	30524 KiB

selling_rna

#include <bits/stdc++.h>
//ako ovaj vaso daso misli da me pobedjuje.....
using namespace std;
#define int long long
#define f first
#define s second
const int N = 1e5 + 69;
const int p = 31;
const int mod = 1e9 + 7;
const int B = 750;
int trie[N][26], node, n, q, inv[N];
vector<int> hsh[N];
string s[N];
int add(int a, int b) {
	a += b;
	if (a >= mod)
		a -= mod;
	return a;
}
int mul(int a, int b) {
	a *= b;
	if (a >= mod)
		a %= mod;
	return a;
}
int sub(int a, int b) {
	a -= b;
	if (a <= 0)
		a += mod;
	return a;
}
int binpow(int a, int b) {
	int res = 1;
	while (b > 0) {
		if (b & 1)
			res = mul(res, a);
		a = mul(a, a);
		b >>= 1;
	}
	return res;
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
  	cin >> n >> q;
  	inv[0] = 1;
  	int t = 1;
  	for (int i = 1;i < N;i++) {
  		t = mul(t, p);
  		inv[i] = binpow(t, mod - 2);
  	}
  	for (int i = 1;i <= n;i++) {
  		cin >> s[i];
  		hsh[i].resize(s[i].size());
  		int t = 1;
  		for (int j = 0;j < (int)s[i].size();j++) {
				if (j > 0)
					hsh[i][j] = hsh[i][j - 1];
				hsh[i][j] = add(hsh[i][j], mul((s[i][j] - 'A' + 1), t));
				t = mul(t, p);
  		}
  	}
  	auto Calc = [&](int i, int L, int R) {
  		if (L == 0)
  			return hsh[i][R];
  		return mul(sub(hsh[i][R], hsh[i][L - 1]), inv[L]);
  	};
  	while (q--) {
  		string x, y;
  		cin >> x >> y;
  		int t = 1, h1 = 0, h2 = 0;
  		for (auto c : x) {
  			h1 = add(h1, mul(c - 'A' + 1, t));
  			t = mul(t, p);
  		}
  		t = 1;
  		for (auto c : y) {
  			h2 = add(h2, mul(c - 'A' + 1, t));
  			t = mul(t, p);
  		}
  		int ans = 0;
  		for (int i = 1;i <= n;i++) {
  			int m = s[i].size();
  			if (x.size() > m || y.size() > m)
  				continue;
  			if (Calc(i, 0, x.size() - 1) == h1 && Calc(i, m - y.size(), m - 1) == h2)
  				++ans;
  		}
  		cout << ans << '\n';
  	}
	}
  return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:88:19: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   88 |      if (x.size() > m || y.size() > m)
      |          ~~~~~~~~~^~~
selling_rna.cpp:88:35: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   88 |      if (x.size() > m || y.size() > m)
      |                          ~~~~~~~~~^~~

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