oj.uz

Submission #343256

# Submission time Handle Problem Language Result Execution time Memory
343256 2021-01-03T15:19:50 Z Millad Selling RNA Strands (JOI16_selling_rna) C++17
10 / 100
 1500 ms 60672 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 = 1e5 + 6, inf = 1e18, mod = 1e9 + 7, mod2 = 1e9 + 9;
ll n, m, pw26[2][maxn];
str s[maxn], t[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(ll k){
	ll sz = t[k].size();
	ll x = 0, x2 = 0;
	for(ll i = 0; i < sz; i ++){
		ll c = t[k][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 ++){
		cin >> t[i * 2] >> t[i * 2 + 1];
		pll p1 = HASH(i * 2);
		pll p2 = HASH(i * 2 + 1);
		ll ans = 0;
		for(ll j = 0; j < n; j ++){
			if(s[j].size() < t[i * 2].size())continue;
			if(s[j].size() < t[i * 2 + 1].size())continue;
			if(v[0][j][t[i * 2].size() - 1] != p1.F)continue;
			if(v[1][j][t[i * 2].size() - 1] != p1.S)continue;
			ll x = v[0][j][s[j].size() - 1];
			ll szj = s[j].size();
			ll szq = t[i * 2 + 1].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 9 ms 12908 KB Output is correct
2 Correct 9 ms 12908 KB Output is correct
3 Correct 9 ms 12908 KB Output is correct
4 Correct 9 ms 12928 KB Output is correct
5 Correct 9 ms 12908 KB Output is correct
6 Correct 9 ms 12908 KB Output is correct
7 Correct 9 ms 12908 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 56812 KB Output is correct
2 Correct 762 ms 60672 KB Output is correct
3 Correct 307 ms 58988 KB Output is correct
4 Correct 382 ms 60524 KB Output is correct
5 Correct 412 ms 41964 KB Output is correct
6 Correct 402 ms 42476 KB Output is correct
7 Correct 573 ms 50412 KB Output is correct
8 Correct 342 ms 59756 KB Output is correct
9 Correct 330 ms 59756 KB Output is correct
10 Execution timed out 1585 ms 56720 KB Time limit exceeded

Subtask #3
0 / 25.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12908 KB Output is correct
2 Correct 9 ms 12908 KB Output is correct
3 Correct 9 ms 12908 KB Output is correct
4 Correct 9 ms 12928 KB Output is correct
5 Correct 9 ms 12908 KB Output is correct
6 Correct 9 ms 12908 KB Output is correct
7 Correct 9 ms 12908 KB Output is correct
8 Correct 193 ms 56812 KB Output is correct
9 Correct 762 ms 60672 KB Output is correct
10 Correct 307 ms 58988 KB Output is correct
11 Correct 382 ms 60524 KB Output is correct
12 Correct 412 ms 41964 KB Output is correct
13 Correct 402 ms 42476 KB Output is correct
14 Correct 573 ms 50412 KB Output is correct
15 Correct 342 ms 59756 KB Output is correct
16 Correct 330 ms 59756 KB Output is correct
17 Execution timed out 1585 ms 56720 KB Time limit exceeded