oj.uz

Submission #343305

# Submission time Handle Problem Language Result Execution time Memory
343305 2021-01-03T16:04:24 Z saniyar_krmi Selling RNA Strands (JOI16_selling_rna) C++14
10 / 100
 1500 ms 143852 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 = 1e6 + 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];

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

inline ll power(const ll &a, const ll &b, const 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;
}

inline void cal(const 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;
	}
}

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

inline pii get2(const int &n, const 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};
}

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

inline 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 370 ms 117740 KB Output is correct
2 Correct 369 ms 117812 KB Output is correct
3 Correct 371 ms 117868 KB Output is correct
4 Correct 380 ms 117868 KB Output is correct
5 Correct 370 ms 117740 KB Output is correct
6 Correct 373 ms 117868 KB Output is correct
7 Correct 371 ms 117868 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 561 ms 143596 KB Output is correct
2 Correct 1102 ms 143852 KB Output is correct
3 Correct 677 ms 143620 KB Output is correct
4 Correct 774 ms 143696 KB Output is correct
5 Correct 657 ms 134252 KB Output is correct
6 Correct 658 ms 134256 KB Output is correct
7 Correct 912 ms 137300 KB Output is correct
8 Correct 708 ms 143724 KB Output is correct
9 Correct 706 ms 143724 KB Output is correct
10 Execution timed out 1560 ms 143672 KB Time limit exceeded

Subtask #3
0 / 25.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 370 ms 117740 KB Output is correct
2 Correct 369 ms 117812 KB Output is correct
3 Correct 371 ms 117868 KB Output is correct
4 Correct 380 ms 117868 KB Output is correct
5 Correct 370 ms 117740 KB Output is correct
6 Correct 373 ms 117868 KB Output is correct
7 Correct 371 ms 117868 KB Output is correct
8 Correct 561 ms 143596 KB Output is correct
9 Correct 1102 ms 143852 KB Output is correct
10 Correct 677 ms 143620 KB Output is correct
11 Correct 774 ms 143696 KB Output is correct
12 Correct 657 ms 134252 KB Output is correct
13 Correct 658 ms 134256 KB Output is correct
14 Correct 912 ms 137300 KB Output is correct
15 Correct 708 ms 143724 KB Output is correct
16 Correct 706 ms 143724 KB Output is correct
17 Execution timed out 1560 ms 143672 KB Time limit exceeded