oj.uz

Submission #343262

# Submission time Handle Problem Language Result Execution time Memory
343262 2021-01-03T15:22:17 Z Millad Selling RNA Strands (JOI16_selling_rna) C++17
10 / 100
 1500 ms 60932 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(int k){
	int sz = s[k].size();
	for(int 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(int k){
	int sz = t[k].size();
	ll x = 0, x2 = 0;
	for(int 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(int 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(int i = 0; i < n; i ++){
		cin >> s[i];
		hAsh(i);
	}
	for(int 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(int 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];
			int szj = s[j].size();
			int szq = t[i * 2 + 1].size();
			int 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 10 ms 12908 KB Output is correct
2 Correct 11 ms 12908 KB Output is correct
3 Correct 9 ms 12908 KB Output is correct
4 Correct 9 ms 12908 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 217 ms 57964 KB Output is correct
2 Correct 857 ms 60756 KB Output is correct
3 Correct 313 ms 59500 KB Output is correct
4 Correct 385 ms 60932 KB Output is correct
5 Correct 419 ms 42628 KB Output is correct
6 Correct 434 ms 42856 KB Output is correct
7 Correct 603 ms 51052 KB Output is correct
8 Correct 343 ms 60396 KB Output is correct
9 Correct 329 ms 60412 KB Output is correct
10 Execution timed out 1562 ms 56812 KB Time limit exceeded

Subtask #3
0 / 25.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12908 KB Output is correct
2 Correct 11 ms 12908 KB Output is correct
3 Correct 9 ms 12908 KB Output is correct
4 Correct 9 ms 12908 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 217 ms 57964 KB Output is correct
9 Correct 857 ms 60756 KB Output is correct
10 Correct 313 ms 59500 KB Output is correct
11 Correct 385 ms 60932 KB Output is correct
12 Correct 419 ms 42628 KB Output is correct
13 Correct 434 ms 42856 KB Output is correct
14 Correct 603 ms 51052 KB Output is correct
15 Correct 343 ms 60396 KB Output is correct
16 Correct 329 ms 60412 KB Output is correct
17 Execution timed out 1562 ms 56812 KB Time limit exceeded