Submission #411784

#	Time	Username	Problem	Language	Result	Execution time	Memory
411784		jjj	Selling RNA Strands (JOI16_selling_rna)	C++14	35 / 100	1575 ms	27212 KiB

selling_rna

#include <bits/stdc++.h>
#define MAXN 100010
#define MOD 1000000007

using namespace std;

string s;

vector < vector <long long> > v;

long long x[MAXN];

int sl(char c)
{
	if(c == 'A') return 1;
	if(c == 'G') return 2;
	if(c == 'C') return 3;
	if(c == 'U') return 4;
}


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	x[0] = 1;
	
	for(int i = 1; i < MAXN; i++) x[i] = (x[i - 1] * 31) % MOD;
	
	int n, m;
	
	cin >> n >> m;
	
	v.resize(n + 1);
	
	for(int i = 0; i < n; i++)
	{
		cin >> s;
		
		int k = s.size();
		
		v[i].push_back(sl(s[0]));
		
		for(int j = 1; j < k; j++) v[i].push_back((v[i][j - 1] + sl(s[j]) * x[j]) % MOD);
	}
	
	for(int i = 0; i < m; i++)
	{
		cin >> s;
		
		long long p = 0, q = 0;
		
		int kp = s.size();
		
		p = sl(s[0]);
		
		for(int j = 1; j < kp; j++) p = (p + x[j] * sl(s[j])) % MOD;
		
		cin >> s;
		
		int kq = s.size();
		
		q = sl(s[0]);
		
		for(int j = 1; j < kq; j++) q = (q + x[j] * sl(s[j])) % MOD;
		
		int S = 0;
		
		for(int j = 0; j < n; j++)
		{
			int V = v[j].size();
			
			if(kp > V || kq > V) continue;
			
			
			if(kq != V && p == v[j][kp - 1] && ((q * x[V - kq]) % MOD) == (v[j][V - 1] - v[j][V - kq - 1] + MOD) % MOD) S++;
			else if(kq == V && p == v[j][kp - 1] && ((q * x[V - kq]) % MOD) == v[j][V - 1]) S++;
		}
		
		cout << S << "\n";
	} 
	
	return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'int sl(char)':
selling_rna.cpp:19:1: warning: control reaches end of non-void function [-Wreturn-type]
   19 | }
      | ^

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40