oj.uz

Submission #343300

# Submission time Handle Problem Language Result Execution time Memory
343300 2021-01-03T15:59:48 Z saniyar_krmi Selling RNA Strands (JOI16_selling_rna) C++14
10 / 100
 1500 ms 261228 KB 
// YOU ONLY GOT ONE SHOT
#include <bits/stdc++.h>
#define put(x) cerr << #x << ": " << x << '\n'
#define line() cerr << "**************\n"
#pragma GCC optimize ("Ofast")

//#define F first
//#define S second
//#define mul(x, y) (((x) * (y)) %mod)
//#define bit(i, j) (((i)>>(j)) &1)
//#define left(id) ((id<<1) + 1)
//#define right(id) ((id<<1) + 2)
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;

const int maxn = 2e6 + 10, mod1 = 1e9 + 9, mod2 = 1e9 + 7, P = 737;
int n, m;
string s[maxn];
vector <int> a[maxn];
int len[maxn];
int p[2][maxn], inv[2][maxn];
vector <int> h[2][maxn];

ll mul(ll a, ll b, ll mod){
	return (a * b) %mod;
}

ll power(ll a, ll b, ll mod){
	ll res = 1;
	for(ll i = 1, pw = a; i <= b; i <<= 1, pw = mul(pw, pw, mod))
		if(b & i)
			res = mul(res, pw, mod);
	return res;
}

void cal(int k){
	len[k] = s[k].size();
	int n = len[k];
	a[k].resize(n);
	h[0][k].resize(n+1);
	h[1][k].resize(n+1);

	for(int i=0; i<n; i++)
		a[k][i] = s[k][i] - 'A' + 1;
	for(int i=0; i<n; i++){
		h[0][k][i+1] = (h[0][k][i] + mul(a[k][i], p[0][i], mod1)) %mod1;
		h[1][k][i+1] = (h[1][k][i] + mul(a[k][i], p[1][i], mod2)) %mod2;
	}
}

pii get1(int n, int i){
	return {h[0][i][n], h[1][i][n]};
}

pii get2(int n, int i){
	int res1 = mul((h[0][i][len[i]] - h[0][i][len[i] - n] + mod1) %mod1, inv[0][len[i] - n], mod1);
	int res2 = mul((h[1][i][len[i]] - h[1][i][len[i] - n] + mod2) %mod2, inv[1][len[i] - n], mod2);
	return {res1, res2};
}

int solve(pii h1, pii h2, int n1, int n2){
	int res = 0;
	for(int i=0; i<n; i++)
		if(get1(n1, i) == h1 && get2(n2, i) == h2)
			res++;
	return res;
}

void pre(){
	p[0][0] = p[1][0] = 1;
	for(int i=1; i<maxn; i++){
		p[0][i] = mul(p[0][i-1], P, mod1);
		p[1][i] = mul(p[1][i-1], P, mod2);
	}
	for(int i=0; i<maxn; i++){
		inv[0][i] = power(p[0][i], mod1-2, mod1);
		inv[1][i] = power(p[1][i], mod2-2, mod2);
	}
}

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);  cout.tie(0);
	pre();

	cin >> n >> m;
	for(int i=0; i<n; i++)
		cin >> s[i], cal(i);

	string pp, q;
	while(m--){
		cin >> pp >> q;

		int n = pp.size(), n1 = pp.size(), n2 = q.size();
		vector <int> b(n);
		for(int i=0; i<n; i++)
			b[i] = pp[i] - 'A'  +1;

		int Hash1[2] = {0, 0}, Hash2[2] = {0, 0};
		for(int i=0; i<n; i++){
			Hash1[0] = (Hash1[0] + mul(b[i], p[0][i], mod1)) %mod1;
			Hash1[1] = (Hash1[1] + mul(b[i], p[1][i], mod2)) %mod2;
		}

		n = q.size();
		b.resize(n);
		for(int i=0; i<n; i++)
			b[i] = q[i] - 'A' + 1;

		for(int i=0; i<n; i++){
			Hash2[0] = (Hash2[0] + mul(b[i], p[0][i], mod1)) %mod1;
			Hash2[1] = (Hash2[1] + mul(b[i], p[1][i], mod2)) %mod2;
		}

		cout << solve({Hash1[0], Hash1[1]}, {Hash2[0], Hash2[1]}, n1, n2) << '\n';
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 745 ms 235204 KB Output is correct
2 Correct 742 ms 235244 KB Output is correct
3 Correct 742 ms 235244 KB Output is correct
4 Correct 742 ms 235244 KB Output is correct
5 Correct 736 ms 235116 KB Output is correct
6 Correct 738 ms 235244 KB Output is correct
7 Correct 758 ms 235244 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 915 ms 261188 KB Output is correct
2 Correct 1435 ms 261100 KB Output is correct
3 Correct 1012 ms 260972 KB Output is correct
4 Correct 1128 ms 261100 KB Output is correct
5 Correct 988 ms 251500 KB Output is correct
6 Correct 989 ms 251756 KB Output is correct
7 Correct 1241 ms 254572 KB Output is correct
8 Correct 1045 ms 261036 KB Output is correct
9 Correct 1042 ms 260972 KB Output is correct
10 Execution timed out 1605 ms 261228 KB Time limit exceeded

Subtask #3
0 / 25.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 745 ms 235204 KB Output is correct
2 Correct 742 ms 235244 KB Output is correct
3 Correct 742 ms 235244 KB Output is correct
4 Correct 742 ms 235244 KB Output is correct
5 Correct 736 ms 235116 KB Output is correct
6 Correct 738 ms 235244 KB Output is correct
7 Correct 758 ms 235244 KB Output is correct
8 Correct 915 ms 261188 KB Output is correct
9 Correct 1435 ms 261100 KB Output is correct
10 Correct 1012 ms 260972 KB Output is correct
11 Correct 1128 ms 261100 KB Output is correct
12 Correct 988 ms 251500 KB Output is correct
13 Correct 989 ms 251756 KB Output is correct
14 Correct 1241 ms 254572 KB Output is correct
15 Correct 1045 ms 261036 KB Output is correct
16 Correct 1042 ms 260972 KB Output is correct
17 Execution timed out 1605 ms 261228 KB Time limit exceeded