oj.uz

답안 #343299

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
343299 2021-01-03T15:59:27 Z S2speed Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 559 ms 32364 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 = 5e3 + 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 1 ms 640 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 1 ms 620 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 133 ms 32236 KB Output is correct
2 Correct 373 ms 32236 KB Output is correct
3 Correct 244 ms 32364 KB Output is correct
4 Correct 298 ms 32364 KB Output is correct
5 Correct 388 ms 20432 KB Output is correct
6 Correct 413 ms 20716 KB Output is correct
7 Correct 210 ms 24428 KB Output is correct
8 Correct 379 ms 32364 KB Output is correct
9 Correct 345 ms 32108 KB Output is correct
10 Correct 559 ms 32236 KB Output is correct

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 10 ms 1004 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 1 ms 640 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 133 ms 32236 KB Output is correct
9 Correct 373 ms 32236 KB Output is correct
10 Correct 244 ms 32364 KB Output is correct
11 Correct 298 ms 32364 KB Output is correct
12 Correct 388 ms 20432 KB Output is correct
13 Correct 413 ms 20716 KB Output is correct
14 Correct 210 ms 24428 KB Output is correct
15 Correct 379 ms 32364 KB Output is correct
16 Correct 345 ms 32108 KB Output is correct
17 Correct 559 ms 32236 KB Output is correct
18 Runtime error 10 ms 1004 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -