oj.uz

Submission #411784

# Submission time Handle Problem Language Result Execution time Memory
411784 2021-05-26T00:17:37 Z jjj Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1500 ms 27212 KB 
#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

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.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 24684 KB Output is correct
2 Correct 568 ms 26940 KB Output is correct
3 Correct 182 ms 25832 KB Output is correct
4 Correct 237 ms 26604 KB Output is correct
5 Correct 288 ms 16940 KB Output is correct
6 Correct 276 ms 17092 KB Output is correct
7 Correct 281 ms 22572 KB Output is correct
8 Correct 273 ms 27212 KB Output is correct
9 Correct 244 ms 27204 KB Output is correct
10 Correct 558 ms 24764 KB Output is correct

Subtask #3
0 / 25.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1100 KB Output is correct
2 Correct 2 ms 1100 KB Output is correct
3 Correct 2 ms 1100 KB Output is correct
4 Correct 2 ms 1100 KB Output is correct
5 Correct 2 ms 1096 KB Output is correct
6 Correct 2 ms 1100 KB Output is correct
7 Correct 2 ms 1100 KB Output is correct
8 Correct 133 ms 24684 KB Output is correct
9 Correct 568 ms 26940 KB Output is correct
10 Correct 182 ms 25832 KB Output is correct
11 Correct 237 ms 26604 KB Output is correct
12 Correct 288 ms 16940 KB Output is correct
13 Correct 276 ms 17092 KB Output is correct
14 Correct 281 ms 22572 KB Output is correct
15 Correct 273 ms 27212 KB Output is correct
16 Correct 244 ms 27204 KB Output is correct
17 Correct 558 ms 24764 KB Output is correct
18 Execution timed out 1575 ms 4292 KB Time limit exceeded
19 Halted 0 ms 0 KB -