oj.uz

Submission #343221

# Submission time Handle Problem Language Result Execution time Memory
343221 2021-01-03T14:32:28 Z S2speed Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 506 ms 32620 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;
};

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];
ll oh[MAX_N] , qh[MAX_N] , sz[MAX_N] , osz[MAX_N] , qsz[MAX_N];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	ll n , m;
	cin>>n>>m;
	if(n >= MAX_N || m >= MAX_N) return 0;
	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;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory 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 620 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

# Verdict Execution time Memory Grader output
1 Correct 122 ms 32620 KB Output is correct
2 Correct 353 ms 32620 KB Output is correct
3 Correct 222 ms 32620 KB Output is correct
4 Correct 280 ms 32584 KB Output is correct
5 Correct 387 ms 20716 KB Output is correct
6 Correct 373 ms 20972 KB Output is correct
7 Correct 194 ms 24556 KB Output is correct
8 Correct 312 ms 32620 KB Output is correct
9 Correct 290 ms 32364 KB Output is correct
10 Correct 506 ms 32492 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory 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 620 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 122 ms 32620 KB Output is correct
9 Correct 353 ms 32620 KB Output is correct
10 Correct 222 ms 32620 KB Output is correct
11 Correct 280 ms 32584 KB Output is correct
12 Correct 387 ms 20716 KB Output is correct
13 Correct 373 ms 20972 KB Output is correct
14 Correct 194 ms 24556 KB Output is correct
15 Correct 312 ms 32620 KB Output is correct
16 Correct 290 ms 32364 KB Output is correct
17 Correct 506 ms 32492 KB Output is correct
18 Incorrect 1 ms 620 KB Output isn't correct
19 Halted 0 ms 0 KB -