Submission #597924

#	Time	Username	Problem	Language	Result	Execution time	Memory
597924		CSQ31	Selling RNA Strands (JOI16_selling_rna)	C++17	Compilation error	0 ms	0 KiB

selling_rna

#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(a[i] > b[i])return 0;
		if(b[i] > a[i])return 2;
	}
	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
		int l = 0,r = n-1;
		while(r>=l){
			int mid = (l+r)/2;
			if(cmp(p,s[mid]) >= 1)r = mid-1;
			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;
			else r=mid-1;
			
		}
		int R = r;
		//cout<<L<<" "<<R<<'\n';
		if(R>=L){
				for(int i=L;i<=R;i++){
					if(pre[i][a-1] == pre && sh[i][b-1] == suf)ans++;
					
				}
			}
		}
		cout<<ans<<'\n';
		
	}
	
	
}

Compilation message (stderr)

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:120:12: error: no match for 'operator[]' (operand types are 'pii' {aka 'std::pair<int, int>'} and 'int')
  120 |      if(pre[i][a-1] == pre && sh[i][b-1] == suf)ans++;
      |            ^
selling_rna.cpp:125:9: error: 'ans' was not declared in this scope; did you mean 'abs'?
  125 |   cout<<ans<<'\n';
      |         ^~~
      |         abs
selling_rna.cpp: At global scope:
selling_rna.cpp:130:1: error: expected declaration before '}' token
  130 | }
      | ^