oj.uz

답안 #343125

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
343125 2021-01-03T12:31:00 Z Parsa_PG Selling RNA Strands (JOI16_selling_rna) C++14
10 / 100
 603 ms 34284 KB 
/* Rastegary Az Shoroe Ye EDAST */
#include <bits/stdc++.h>
     
#define pb push_back
#define endl "\n"
#define ll long long
 
using namespace std;
 
const int maxn = 5e3 + 10 , Maxn = 1e5 + 10, lg = 22 , p = 17;
const int mod = 22777;
const ll inf = 1e18 + 10;
 
int bpw[maxn] , psum[maxn][Maxn];
 
void PG(){
	bpw[0] = 1;
	for(int i = 1 ; i < maxn ; i++)
		bpw[i] = (bpw[i - 1]*p)%mod;
}
 
int check(char c){
	if(c == 'A')
		return 0;
	if(c == 'C')
		return 1;
	if(c == 'G')
		return 2;
	return 3;
}
 
int32_t main(){
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n , m;
	cin >> n >> m;
	PG();
	string s[maxn];
	for(int i = 0 ; i < n ; i ++){
		cin >> s[i];
		psum[i][0] = check(s[i][0]);
		for(int j = 1 ; j < (int)s[i].size() ; j++)
			psum[i][j] = (psum[i][j - 1] + ((check(s[i][j]) * bpw[j]) % mod))% mod;
	}
	string p , q;
	while(m--){
		cin >> p >> q;
		int ph = check(p[0]) , qh = check(q[0]);
		for(int i = 1 ; i < (int)p.size() ; i++)
			ph = (ph + (bpw[i] * check(p[i])) % mod) % mod; 
		for(int i = 1 ; i < (int)q.size() ; i++)
			qh = (qh + (bpw[i] * check(q[i])) % mod) % mod; 
		int ans = 0;
		for(int i = 0 ; i < n ; i++){
			if(s[i].size() < q.size() || s[i].size() < p.size())
				continue;
			int pref = psum[i][p.size() - 1];
			int suf = (psum[i][s[i].size() - 1] - psum[i][s[i].size() - q.size() - 1] + mod) % mod;
			if(pref == ph && ((qh * bpw[s[i].size() - q.size()] ) % mod) == suf)
				ans++;
		}
		cout << ans << endl;
	}
	return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1004 KB Output is correct
2 Correct 1 ms 1004 KB Output is correct
3 Correct 1 ms 1004 KB Output is correct
4 Correct 1 ms 1004 KB Output is correct
5 Correct 1 ms 1004 KB Output is correct
6 Correct 1 ms 1004 KB Output is correct
7 Correct 1 ms 1004 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 117 ms 19948 KB Output is correct
2 Correct 603 ms 34156 KB Output is correct
3 Correct 243 ms 25708 KB Output is correct
4 Correct 327 ms 34284 KB Output is correct
5 Incorrect 408 ms 30444 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 63 ms 30572 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1004 KB Output is correct
2 Correct 1 ms 1004 KB Output is correct
3 Correct 1 ms 1004 KB Output is correct
4 Correct 1 ms 1004 KB Output is correct
5 Correct 1 ms 1004 KB Output is correct
6 Correct 1 ms 1004 KB Output is correct
7 Correct 1 ms 1004 KB Output is correct
8 Correct 117 ms 19948 KB Output is correct
9 Correct 603 ms 34156 KB Output is correct
10 Correct 243 ms 25708 KB Output is correct
11 Correct 327 ms 34284 KB Output is correct
12 Incorrect 408 ms 30444 KB Output isn't correct
13 Halted 0 ms 0 KB -