oj.uz

Submission #343298

# Submission time Handle Problem Language Result Execution time Memory
343298 2021-01-03T15:58:26 Z saniyar_krmi Selling RNA Strands (JOI16_selling_rna) C++14
10 / 100
 1500 ms 315884 KB 
// YOU ONLY GOT ONE SHOT
#include <bits/stdc++.h>
#define put(x) cerr << #x << ": " << x << '\n'
#define line() cerr << "**************\n"
#define int long long 

//#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 766 ms 266604 KB Output is correct
2 Correct 757 ms 266604 KB Output is correct
3 Correct 778 ms 266476 KB Output is correct
4 Correct 762 ms 266476 KB Output is correct
5 Correct 759 ms 266476 KB Output is correct
6 Correct 753 ms 266604 KB Output is correct
7 Correct 751 ms 266476 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1008 ms 315756 KB Output is correct
2 Execution timed out 1621 ms 315884 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 766 ms 266604 KB Output is correct
2 Correct 757 ms 266604 KB Output is correct
3 Correct 778 ms 266476 KB Output is correct
4 Correct 762 ms 266476 KB Output is correct
5 Correct 759 ms 266476 KB Output is correct
6 Correct 753 ms 266604 KB Output is correct
7 Correct 751 ms 266476 KB Output is correct
8 Correct 1008 ms 315756 KB Output is correct
9 Execution timed out 1621 ms 315884 KB Time limit exceeded
10 Halted 0 ms 0 KB -