oj.uz

Submission #597933

# Submission time Handle Problem Language Result Execution time Memory
597933 2022-07-17T07:48:00 Z CSQ31 Selling RNA Strands (JOI16_selling_rna) C++17
60 / 100
 1500 ms 38916 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 2;
		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(sh[i][b-1] == suf)ans++;
		
		cout<<ans<<'\n';
		
	}
	
	
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:96:7: warning: variable 'pre' set but not used [-Wunused-but-set-variable]
   96 |   pii pre = make_hash(p);
      |       ^~~
selling_rna.cpp:99:7: warning: unused variable 'a' [-Wunused-variable]
   99 |   int a = p.size();
      |       ^

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 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 34004 KB Output is correct
2 Correct 185 ms 34232 KB Output is correct
3 Correct 104 ms 34060 KB Output is correct
4 Correct 115 ms 34280 KB Output is correct
5 Correct 54 ms 21620 KB Output is correct
6 Correct 54 ms 21860 KB Output is correct
7 Correct 181 ms 25524 KB Output is correct
8 Correct 112 ms 34276 KB Output is correct
9 Correct 114 ms 34092 KB Output is correct
10 Correct 271 ms 34264 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1478 ms 7652 KB Output is correct
2 Correct 636 ms 5520 KB Output is correct
3 Correct 973 ms 7100 KB Output is correct
4 Correct 335 ms 5584 KB Output is correct
5 Correct 216 ms 5692 KB Output is correct
6 Correct 293 ms 7120 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 115 ms 34004 KB Output is correct
9 Correct 185 ms 34232 KB Output is correct
10 Correct 104 ms 34060 KB Output is correct
11 Correct 115 ms 34280 KB Output is correct
12 Correct 54 ms 21620 KB Output is correct
13 Correct 54 ms 21860 KB Output is correct
14 Correct 181 ms 25524 KB Output is correct
15 Correct 112 ms 34276 KB Output is correct
16 Correct 114 ms 34092 KB Output is correct
17 Correct 271 ms 34264 KB Output is correct
18 Correct 1478 ms 7652 KB Output is correct
19 Correct 636 ms 5520 KB Output is correct
20 Correct 973 ms 7100 KB Output is correct
21 Correct 335 ms 5584 KB Output is correct
22 Correct 216 ms 5692 KB Output is correct
23 Correct 293 ms 7120 KB Output is correct
24 Correct 853 ms 38916 KB Output is correct
25 Execution timed out 1568 ms 38812 KB Time limit exceeded
26 Halted 0 ms 0 KB -