oj.uz

Submission #343303

# Submission time Handle Problem Language Result Execution time Memory
343303 2021-01-03T16:01:52 Z S2speed Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 578 ms 36936 KB 
#include<bits/stdc++.h>
#include<fstream>
 
using namespace std;

#pragma GCC optimize ("Ofast")

#define all(x) x.begin() , x.end()
#define gcd __gcd 
typedef long long int ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;
typedef long double db;
struct piii {
	int first , second , third;
};
typedef pair<pii , pii> piiii;

const ll MAX_N = 1e5 + 20 , md = 1100000123;
 
ll tav(ll n , ll k){
	ll res = 1;
	while(k > 0){
		if(k & 1){
			res *= n;
		}
		n *= n;
		k /= 2;
	}
	return res;
}

vector<ll> ph[MAX_N] , sh[MAX_N] , p , s;
ll oo , qq , sz[MAX_N] , x = 0 , qh[MAX_N] , oh[MAX_N] , osz[MAX_N] , qsz[MAX_N];
map<piiii , int> mp;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	ll n , m , sq;
	cin>>n>>m; sq = sqrt(n);
	if(n <= 5e3 || m <= 5e3){
		for(int i = 0 ; i < n ; i++){
			string s;
			cin>>s;
			ll h = s.size(); sz[i] = h;
			for(int j = 0 ; j < h ; j++){
				if(s[j] == 'A'){
					s[j] = 0;
				}
				if(s[j] == 'C'){
					s[j] = 1;
				}
				if(s[j] == 'G'){
					s[j] = 2;
				}
				if(s[j] == 'U'){
					s[j] = 3;
				}
			}
			ll t = 1 , hash = 0;
			ph[i].resize(h); sh[i].resize(h);
			for(int j = 0 ; j < h ; j++){
				hash += 1ll * t * s[j]; hash %= md;
				t *= 4; t %= md;
				ph[i][j] = hash;
			}
			hash = 0; t = 1;
			for(int j = h - 1 ; j >= 0 ; j--){
				hash += 1ll * t * s[j]; hash %= md;
				t *= 4; t %= md;
				sh[i][j] = hash;
			}
		}
		for(int i = 0 ; i < m ; i++){
			string o , q;
			cin>>o>>q;
			ll hash = 0 , t = 1 , os = o.size() , qs = q.size(); osz[i] = os; qsz[i] = qs;
			for(int j = 0 ; j < os ; j++){
				if(o[j] == 'A'){
					o[j] = 0;
				}
				if(o[j] == 'C'){
					o[j] = 1;
				}
				if(o[j] == 'G'){
					o[j] = 2;
				}
				if(o[j] == 'U'){
					o[j] = 3;
				}
			}
			for(int j = 0 ; j < qs ; j++){
				if(q[j] == 'A'){
					q[j] = 0;
				}
				if(q[j] == 'C'){
					q[j] = 1;
				}
				if(q[j] == 'G'){
					q[j] = 2;
				}
				if(q[j] == 'U'){
					q[j] = 3;
				}
			}
			for(int j = 0 ; j < os ; j++){
				hash += 1ll * t * o[j]; hash %= md;
				t *= 4; t %= md;
			}
			oh[i] = hash;
			hash = 0; t = 1;
			for(int j = qs - 1 ; j >= 0 ; j--){
				hash += 1ll * t * q[j]; hash %= md;
				t *= 4; t %= md;
			}
			qh[i] = hash;
		}
		for(int i = 0 ; i < m ; i++){
			ll cnt = 0;
			for(int j = 0 ; j < n ; j++){
				if(osz[i] > sz[j] || qsz[i] > sz[j]) continue;
				if(oh[i] != ph[j][osz[i] - 1]) continue;
				if(qh[i] != sh[j][sz[j] - qsz[i]]) continue;
				cnt++;
			}
			cout<<cnt<<'\n';
		}
		return 0;
	}
	for(int i = 0 ; i < n ; i++){
		string s;
		cin>>s;
		ll h = s.size();
		if(h < sq){
			for(int j = 0 ; j < h ; j++){
				if(s[j] == 'A'){
					s[j] = 0;
				}
				if(s[j] == 'C'){
					s[j] = 1;
				}
				if(s[j] == 'G'){
					s[j] = 2;
				}
				if(s[j] == 'U'){
					s[j] = 3;
				}
			}
			ll t = 1 , hash = 0;
			p.resize(h); s.resize(h);
			for(int j = 0 ; j < h ; j++){
				hash += 1ll * t * s[j]; hash %= md;
				t *= 4; t %= md;
				p[j] = hash;
			}
			hash = 0; t = 1;
			for(int j = h - 1 ; j >= 0 ; j--){
				hash += 1ll * t * s[j]; hash %= md;
				t *= 4; t %= md;
				s[j] = hash;
			}
			for(int i = 0 ; i < h ; i++){
				for(int j = 0 ; j < h ; j++){
					mp[{{i , j} , {p[i] , s[i]}}]++;
				}
			}
			continue;
		}
		sz[x] = h;
		for(int j = 0 ; j < h ; j++){
			if(s[j] == 'A'){
				s[j] = 0;
			}
			if(s[j] == 'C'){
				s[j] = 1;
			}
			if(s[j] == 'G'){
				s[j] = 2;
			}
			if(s[j] == 'U'){
				s[j] = 3;
			}
		}
		ll t = 1 , hash = 0;
		ph[x].resize(h); sh[x].resize(h);
		for(int j = 0 ; j < h ; j++){
			hash += 1ll * t * s[j]; hash %= md;
			t *= 4; t %= md;
			ph[x][j] = hash;
		}
		hash = 0; t = 1;
		for(int j = h - 1 ; j >= 0 ; j--){
			hash += 1ll * t * s[j]; hash %= md;
			t *= 4; t %= md;
			sh[x][j] = hash;
		}
		x++;
	}
	for(int i = 0 ; i < m ; i++){
		string o , q;
		cin>>o>>q;
		ll hash = 0 , t = 1 , os = o.size() , qs = q.size(); osz[i] = os; qsz[i] = qs;
		for(int j = 0 ; j < os ; j++){
			if(o[j] == 'A'){
				o[j] = 0;
			}
			if(o[j] == 'C'){
				o[j] = 1;
			}
			if(o[j] == 'G'){
				o[j] = 2;
			}
			if(o[j] == 'U'){
				o[j] = 3;
			}
		}
		for(int j = 0 ; j < qs ; j++){
			if(q[j] == 'A'){
				q[j] = 0;
			}
			if(q[j] == 'C'){
				q[j] = 1;
			}
			if(q[j] == 'G'){
				q[j] = 2;
			}
			if(q[j] == 'U'){
				q[j] = 3;
			}
		}
		for(int j = 0 ; j < os ; j++){
			hash += 1ll * t * o[j]; hash %= md;
			t *= 4; t %= md;
		}
		oo = hash;
		hash = 0; t = 1;
		for(int j = qs - 1 ; j >= 0 ; j--){
			hash += 1ll * t * q[j]; hash %= md;
			t *= 4; t %= md;
		}
		qq = hash;
		ll ans = mp[{{os , qs} , {oo , qq}}];
		for(int i = 0 ; i < m ; i++){
			for(int j = 0 ; j < n ; j++){
				if(osz[i] > sz[j] || qsz[i] > sz[j]) continue;
				if(oh[i] != ph[j][osz[i] - 1]) continue;
				if(qh[i] != sh[j][sz[j] - qsz[i]]) continue;
				ans++;
			}
			cout<<ans<<'\n';
		}
	}
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Correct 4 ms 5100 KB Output is correct
7 Correct 4 ms 5100 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 36560 KB Output is correct
2 Correct 373 ms 36856 KB Output is correct
3 Correct 245 ms 36844 KB Output is correct
4 Correct 310 ms 36724 KB Output is correct
5 Correct 419 ms 24940 KB Output is correct
6 Correct 408 ms 25120 KB Output is correct
7 Correct 219 ms 28780 KB Output is correct
8 Correct 374 ms 36716 KB Output is correct
9 Correct 352 ms 36716 KB Output is correct
10 Correct 578 ms 36936 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 9964 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Correct 4 ms 5100 KB Output is correct
7 Correct 4 ms 5100 KB Output is correct
8 Correct 135 ms 36560 KB Output is correct
9 Correct 373 ms 36856 KB Output is correct
10 Correct 245 ms 36844 KB Output is correct
11 Correct 310 ms 36724 KB Output is correct
12 Correct 419 ms 24940 KB Output is correct
13 Correct 408 ms 25120 KB Output is correct
14 Correct 219 ms 28780 KB Output is correct
15 Correct 374 ms 36716 KB Output is correct
16 Correct 352 ms 36716 KB Output is correct
17 Correct 578 ms 36936 KB Output is correct
18 Runtime error 18 ms 9964 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -