Submission #343303

#	Time	Username	Problem	Language	Result	Execution time	Memory
343303		S2speed	Selling RNA Strands (JOI16_selling_rna)	C++17	35 / 100	578 ms	36936 KiB

selling_rna

#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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40