oj.uz

Submission #343252

# Submission time Handle Problem Language Result Execution time Memory
343252 2021-01-03T15:14:29 Z Millad Selling RNA Strands (JOI16_selling_rna) C++14
10 / 100
 1500 ms 139884 KB 
// In the name of god
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define Sort(x) sort(all(x))
#define debug(x) cerr << #x << " : " << x << "\n"
#define use_file freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef string str;

const ll maxn = 1e6 + 6, inf = 1e18, mod = 1e9 + 7, mod2 = 1e9 + 9;
ll n, m, pw26[2][maxn];
str s[maxn];
vector <ll> v[2][maxn];
void hAsh(ll k){
	ll sz = s[k].size();
	for(ll i = 0; i < sz; i ++){
		ll c = s[k][i] - 'A';
		v[0][k].pb(c * pw26[0][i] % mod);
		v[1][k].pb(c * pw26[1][i] % mod2);
		if(i > 0)(v[0][k][i] += v[0][k][i - 1]) %= mod;
		if(i > 0)(v[1][k][i] += v[1][k][i - 1]) %= mod2;
	}
}
pll HASH(str st){
	ll sz = st.size();
	ll x = 0, x2 = 0;
	for(ll i = 0; i < sz; i ++){
		ll c = st[i] - 'A';
		(x += c * pw26[0][i] % mod) %= mod;
		(x2 += c * pw26[1][i] % mod2) %= mod2;
	}
	pll pr = {x, x2};
	return pr;
}
int main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	pw26[0][0] = 1;
	pw26[1][0] = 1;
	ll z = 26;
	for(ll i = 1; i < maxn; i ++){
		pw26[0][i] = (pw26[0][i - 1] * z % mod);
		pw26[1][i] = (pw26[1][i - 1] * z % mod2);
	}
	cin >> n >> m;
	for(ll i = 0; i < n; i ++){
		cin >> s[i];
		hAsh(i);
	}
	for(ll i = 0; i < m; i ++){
		str p, q;
		cin >> p >> q;
		pll p1 = HASH(p);
		pll p2 = HASH(q);
		ll ans = 0;
		for(ll j = 0; j < n; j ++){
			if(s[j].size() < p.size())continue;
			if(s[j].size() < q.size())continue;
			if(v[0][j][p.size() - 1] != p1.F)continue;
			if(v[1][j][p.size() - 1] != p1.S)continue;
			ll x = v[0][j][s[j].size() - 1];
			ll szj = s[j].size();
			ll szq = q.size();
			ll dif = szj;
			dif -= szq;
			if(dif)x = (x - v[0][j][dif - 1] + mod) % mod;
         if((p2.F * pw26[0][dif] % mod) != x)continue;
			x = v[1][j][s[j].size() - 1];
			if(dif)x = (x - v[1][j][dif - 1] + mod2) % mod2;
			if((p2.S * pw26[1][dif] % mod2) != x)continue;
			ans ++;
		}
		cout << ans << "\n";
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 94316 KB Output is correct
2 Correct 60 ms 94316 KB Output is correct
3 Correct 61 ms 94316 KB Output is correct
4 Correct 59 ms 94316 KB Output is correct
5 Correct 60 ms 94316 KB Output is correct
6 Correct 62 ms 94316 KB Output is correct
7 Correct 60 ms 94316 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 136300 KB Output is correct
2 Correct 739 ms 139884 KB Output is correct
3 Correct 348 ms 138476 KB Output is correct
4 Correct 413 ms 139884 KB Output is correct
5 Correct 466 ms 122220 KB Output is correct
6 Correct 434 ms 122476 KB Output is correct
7 Correct 616 ms 127852 KB Output is correct
8 Correct 392 ms 137256 KB Output is correct
9 Correct 372 ms 137196 KB Output is correct
10 Execution timed out 1565 ms 137232 KB Time limit exceeded

Subtask #3
0 / 25.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 94316 KB Output is correct
2 Correct 60 ms 94316 KB Output is correct
3 Correct 61 ms 94316 KB Output is correct
4 Correct 59 ms 94316 KB Output is correct
5 Correct 60 ms 94316 KB Output is correct
6 Correct 62 ms 94316 KB Output is correct
7 Correct 60 ms 94316 KB Output is correct
8 Correct 239 ms 136300 KB Output is correct
9 Correct 739 ms 139884 KB Output is correct
10 Correct 348 ms 138476 KB Output is correct
11 Correct 413 ms 139884 KB Output is correct
12 Correct 466 ms 122220 KB Output is correct
13 Correct 434 ms 122476 KB Output is correct
14 Correct 616 ms 127852 KB Output is correct
15 Correct 392 ms 137256 KB Output is correct
16 Correct 372 ms 137196 KB Output is correct
17 Execution timed out 1565 ms 137232 KB Time limit exceeded