oj.uz

Submission #597931

# Submission time Handle Problem Language Result Execution time Memory
597931 2022-07-17T07:46:56 Z CSQ31 Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 34376 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 cmp(string &a,string &b){
	int n = a.size();
	int m = b.size();
	for(int i=0;i<n;i++){
		if(i==m)return 1;//equal
		if(b[i] > a[i])return 0; //a is smaller 
		if(a[i] > b[i])return 2; //a is bigger
	}
	return 1;
	
}
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];
	sort(s.begin(),s.end());
	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};
		for(int j=0;j<k;j++){
			int c = 1;
			if(s[i][k-j-1] == 'C')c=2;
			else if(s[i][k-j-1] == 'G')c=3;
			else if(s[i][k-j-1] == '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;
		}
	}
	//for(string x:s)cout<<x<<" ";
	//cout<<'\n';
	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();
		//binary search for borders l and r
		/*
			cout<<"comps"<<'\n';
			for(int i=0;i<n;i++)cout<<cmp(p,s[i])<<" ";
			cout<<'\n';
		*/
		//this is 2222211111000000 finding a range of 11111111
		int l = 0,r = n-1;
		while(r>=l){
			int mid = (l+r)/2;
			if(cmp(p,s[mid]) <=1 )r = mid-1; //p >= s[mid];
			else l=mid+1;
		}//first guy >= p
		int L = l;
		l = 0,r = n-1;
		while(r>=l){
			int mid = (l+r)/2;
			if(cmp(p,s[mid]) >=1)l= mid+1; //p <= s[mid]
			else r=mid-1;
			
		}
		int R = r;
		//last guy <= p
		//cout<<L<<" "<<R<<'\n';
		for(int i=L;i<=R;i++)if(ph[i][a-1] == pre && sh[i][b-1] == suf)ans++;
		
		cout<<ans<<'\n';
		
	}
	
	
}

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 33924 KB Output is correct
2 Correct 281 ms 34300 KB Output is correct
3 Correct 107 ms 34068 KB Output is correct
4 Correct 121 ms 34292 KB Output is correct
5 Correct 61 ms 21556 KB Output is correct
6 Correct 60 ms 21900 KB Output is correct
7 Correct 211 ms 25676 KB Output is correct
8 Correct 129 ms 34228 KB Output is correct
9 Correct 139 ms 34124 KB Output is correct
10 Correct 419 ms 34376 KB Output is correct

Subtask #3
0 / 25.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 224 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 144 ms 33924 KB Output is correct
9 Correct 281 ms 34300 KB Output is correct
10 Correct 107 ms 34068 KB Output is correct
11 Correct 121 ms 34292 KB Output is correct
12 Correct 61 ms 21556 KB Output is correct
13 Correct 60 ms 21900 KB Output is correct
14 Correct 211 ms 25676 KB Output is correct
15 Correct 129 ms 34228 KB Output is correct
16 Correct 139 ms 34124 KB Output is correct
17 Correct 419 ms 34376 KB Output is correct
18 Execution timed out 1586 ms 7584 KB Time limit exceeded
19 Halted 0 ms 0 KB -