oj.uz

답안 #343296

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
343296 2021-01-03T15:55:00 Z Millad Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1500 ms 40556 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 <int> 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

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 12908 KB Output is correct
2 Correct 10 ms 12908 KB Output is correct
3 Correct 9 ms 12908 KB Output is correct
4 Correct 10 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
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 203 ms 38252 KB Output is correct
2 Correct 809 ms 40556 KB Output is correct
3 Correct 307 ms 40044 KB Output is correct
4 Correct 380 ms 40428 KB Output is correct
5 Correct 419 ms 29548 KB Output is correct
6 Correct 328 ms 29676 KB Output is correct
7 Correct 545 ms 36332 KB Output is correct
8 Correct 399 ms 40044 KB Output is correct
9 Correct 376 ms 39924 KB Output is correct
10 Correct 1139 ms 37688 KB Output is correct

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1569 ms 16108 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 12908 KB Output is correct
2 Correct 10 ms 12908 KB Output is correct
3 Correct 9 ms 12908 KB Output is correct
4 Correct 10 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 203 ms 38252 KB Output is correct
9 Correct 809 ms 40556 KB Output is correct
10 Correct 307 ms 40044 KB Output is correct
11 Correct 380 ms 40428 KB Output is correct
12 Correct 419 ms 29548 KB Output is correct
13 Correct 328 ms 29676 KB Output is correct
14 Correct 545 ms 36332 KB Output is correct
15 Correct 399 ms 40044 KB Output is correct
16 Correct 376 ms 39924 KB Output is correct
17 Correct 1139 ms 37688 KB Output is correct
18 Execution timed out 1569 ms 16108 KB Time limit exceeded
19 Halted 0 ms 0 KB -