oj.uz

Submission #914302

# Submission time Handle Problem Language Result Execution time Memory
914302 2024-01-21T14:59:52 Z OAleksa Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1500 ms 30524 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 13 ms 6748 KB Output is correct
2 Correct 13 ms 6788 KB Output is correct
3 Correct 13 ms 6748 KB Output is correct
4 Correct 13 ms 6748 KB Output is correct
5 Correct 13 ms 6792 KB Output is correct
6 Correct 13 ms 6748 KB Output is correct
7 Correct 16 ms 6788 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 24400 KB Output is correct
2 Correct 292 ms 25364 KB Output is correct
3 Correct 139 ms 28308 KB Output is correct
4 Correct 220 ms 28548 KB Output is correct
5 Correct 207 ms 20308 KB Output is correct
6 Correct 196 ms 20560 KB Output is correct
7 Correct 172 ms 25428 KB Output is correct
8 Correct 226 ms 30340 KB Output is correct
9 Correct 187 ms 30524 KB Output is correct
10 Correct 307 ms 28008 KB Output is correct

Subtask #3
0 / 25.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 6748 KB Output is correct
2 Correct 13 ms 6788 KB Output is correct
3 Correct 13 ms 6748 KB Output is correct
4 Correct 13 ms 6748 KB Output is correct
5 Correct 13 ms 6792 KB Output is correct
6 Correct 13 ms 6748 KB Output is correct
7 Correct 16 ms 6788 KB Output is correct
8 Correct 84 ms 24400 KB Output is correct
9 Correct 292 ms 25364 KB Output is correct
10 Correct 139 ms 28308 KB Output is correct
11 Correct 220 ms 28548 KB Output is correct
12 Correct 207 ms 20308 KB Output is correct
13 Correct 196 ms 20560 KB Output is correct
14 Correct 172 ms 25428 KB Output is correct
15 Correct 226 ms 30340 KB Output is correct
16 Correct 187 ms 30524 KB Output is correct
17 Correct 307 ms 28008 KB Output is correct
18 Execution timed out 1557 ms 8372 KB Time limit exceeded
19 Halted 0 ms 0 KB -