oj.uz

답안 #343307

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
343307 2021-01-03T16:05:03 Z S2speed Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 557 ms 48748 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<pii , int> mp[500][500];

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[j]}]++;
				}
			}
			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 12 ms 16748 KB Output is correct
2 Correct 11 ms 16748 KB Output is correct
3 Correct 11 ms 16748 KB Output is correct
4 Correct 12 ms 16748 KB Output is correct
5 Correct 12 ms 16748 KB Output is correct
6 Correct 11 ms 16748 KB Output is correct
7 Correct 12 ms 16748 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 141 ms 48236 KB Output is correct
2 Correct 380 ms 48620 KB Output is correct
3 Correct 250 ms 48492 KB Output is correct
4 Correct 315 ms 48748 KB Output is correct
5 Correct 426 ms 36588 KB Output is correct
6 Correct 421 ms 36972 KB Output is correct
7 Correct 229 ms 40556 KB Output is correct
8 Correct 383 ms 48748 KB Output is correct
9 Correct 382 ms 48492 KB Output is correct
10 Correct 557 ms 48620 KB Output is correct

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 39 ms 33772 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 12 ms 16748 KB Output is correct
2 Correct 11 ms 16748 KB Output is correct
3 Correct 11 ms 16748 KB Output is correct
4 Correct 12 ms 16748 KB Output is correct
5 Correct 12 ms 16748 KB Output is correct
6 Correct 11 ms 16748 KB Output is correct
7 Correct 12 ms 16748 KB Output is correct
8 Correct 141 ms 48236 KB Output is correct
9 Correct 380 ms 48620 KB Output is correct
10 Correct 250 ms 48492 KB Output is correct
11 Correct 315 ms 48748 KB Output is correct
12 Correct 426 ms 36588 KB Output is correct
13 Correct 421 ms 36972 KB Output is correct
14 Correct 229 ms 40556 KB Output is correct
15 Correct 383 ms 48748 KB Output is correct
16 Correct 382 ms 48492 KB Output is correct
17 Correct 557 ms 48620 KB Output is correct
18 Runtime error 39 ms 33772 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -