oj.uz

Submission #597919

# Submission time Handle Problem Language Result Execution time Memory
597919 2022-07-17T06:58:36 Z CSQ31 Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 40068 KB 
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef pair<int,int> pii;
const int MOD1 = 1e9+7;
int MOD2;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
pii make_hash(string s){
	int n = s.size();
	int z1 = 5;
	int z2 = 5;
	pii hb;
	for(int i=0;i<n;i++){
		int c = 1;
		if(s[i] == 'C')c=2;
		else if(s[i] == 'G')c=3;
		else if(s[i] == 'U')c=4;
		hb.fi += c * 1LL * z1%MOD1;
		hb.se += c * 1LL * z2%MOD2;
		if(hb.fi>=MOD1)hb.fi-=MOD1;
		if(hb.se>=MOD2)hb.se-=MOD2;
		
		z1 = z1 * 1LL * 5 %MOD1;
		z2 = z2 * 1LL * 5 %MOD2;
	}
	return hb;
	
	
}
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n,m;
	cin>>n>>m;
	MOD2 = uniform_int_distribution<int>(1e8,1e9)(rng);
	vector<string>s(n);
	for(int i=0;i<n;i++)cin>>s[i];
	vector<vector<pii>>ph(n),sh(n); //prefix and suffix hash
	for(int i=0;i<n;i++){
		int k = s[i].size();
		ph[i].resize(k);
		sh[i].resize(k);
		int z1 = 5;
		int z2 = 5;
		pii hb;
		for(int j=0;j<k;j++){
			int c = 1;
			if(s[i][j] == 'C')c=2;
			else if(s[i][j] == 'G')c=3;
			else if(s[i][j] == 'U')c=4;
			hb.fi += c * 1LL * z1%MOD1;
			hb.se += c * 1LL * z2%MOD2;
			if(hb.fi>=MOD1)hb.fi-=MOD1;
			if(hb.se>=MOD2)hb.se-=MOD2;
			
			z1 = z1 * 1LL * 5 %MOD1;
			z2 = z2 * 1LL * 5 %MOD2;
			ph[i][j] = hb;
		}
		z1 = 5;
		z2 = 5;
		hb = {0,0};
		reverse(s[i].begin(),s[i].end());
		for(int j=0;j<k;j++){
			int c = 1;
			if(s[i][j] == 'C')c=2;
			else if(s[i][j] == 'G')c=3;
			else if(s[i][j] == 'U')c=4;
			hb.fi += c * 1LL * z1%MOD1;
			hb.se += c * 1LL * z2%MOD2;
			if(hb.fi>=MOD1)hb.fi-=MOD1;
			if(hb.se>=MOD2)hb.se-=MOD2;
			
			z1 = z1 * 1LL * 5 %MOD1;
			z2 = z2 * 1LL * 5 %MOD2;
			sh[i][j] = hb;
		}
	}
	while(m--){
		
		string p,q;
		cin>>p>>q;
		reverse(q.begin(),q.end());
		pii pre = make_hash(p);
		pii suf = make_hash(q);
		int ans = 0;
		int a = p.size();
		int b = q.size();
		for(int i=0;i<n;i++){
			if(s[i].length() >= max(a,b)){
				if(ph[i][a-1] == pre && sh[i][b-1] == suf)ans++; 
				
			}
		}
		cout<<ans<<'\n';
		
	}
	
	
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:91:21: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
   91 |    if(s[i].length() >= max(a,b)){
      |       ~~~~~~~~~~~~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 34004 KB Output is correct
2 Correct 282 ms 38240 KB Output is correct
3 Correct 186 ms 37948 KB Output is correct
4 Correct 230 ms 38236 KB Output is correct
5 Correct 210 ms 24044 KB Output is correct
6 Correct 295 ms 24364 KB Output is correct
7 Correct 194 ms 30904 KB Output is correct
8 Correct 296 ms 40068 KB Output is correct
9 Correct 255 ms 40008 KB Output is correct
10 Correct 448 ms 37704 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1580 ms 7512 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 106 ms 34004 KB Output is correct
9 Correct 282 ms 38240 KB Output is correct
10 Correct 186 ms 37948 KB Output is correct
11 Correct 230 ms 38236 KB Output is correct
12 Correct 210 ms 24044 KB Output is correct
13 Correct 295 ms 24364 KB Output is correct
14 Correct 194 ms 30904 KB Output is correct
15 Correct 296 ms 40068 KB Output is correct
16 Correct 255 ms 40008 KB Output is correct
17 Correct 448 ms 37704 KB Output is correct
18 Execution timed out 1580 ms 7512 KB Time limit exceeded
19 Halted 0 ms 0 KB -