Submission #1138521

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138521		SmuggingSpun	Selling RNA Strands (JOI16_selling_rna)	C++20	35 / 100	354 ms	19788 KiB

selling_rna

#include<bits/stdc++.h>
#define taskname "B"
using namespace std;
typedef long long ll;
int n, m;
namespace sub12{
	const int mod = 1e9 + 33;
	const int base = 397;
	const int lim = 5e3 + 5;
	const int LIM = 2e6 + 5;
	int pw[LIM];
	vector<int>hash[lim];
	int get_hash(int id, int l, int r){
		return (ll(hash[id][r]) - 1LL * hash[id][l - 1] * pw[r - l + 1] + 1LL * mod * mod) % mod;
	}
	void solve(){
		for(int i = pw[0] = 1; i < LIM; i++){
			pw[i] = 1LL * pw[i - 1] * base % mod;
		}
		for(int i = 0; i < n; i++){
			string s;
			cin >> s;
			hash[i].emplace_back(0);
			for(int j = 0; j < s.size(); j++){
				hash[i].emplace_back((1LL * hash[i].back() * base + s[j]) % mod);
			}
		}
		for(int _ = 0; _ < m; _++){
			string p, q;
			cin >> p >> q;
			int ans = 0, P = 0, Q = 0;
			for(int i = 0; i < p.size(); i++){
				P = (1LL * P * base + p[i]) % mod;
			}
			for(int i = 0; i < q.size(); i++){
				Q = (1LL * Q * base + q[i]) % mod;
			}
			for(int i = 0; i < n; i++){
				if(hash[i].size() > max(p.size(), q.size()) && get_hash(i, 1, p.size()) == P && get_hash(i, int(hash[i].size()) - int(q.size()), int(hash[i].size()) - 1) == Q){
					ans++;
				}
			}
			cout << ans << "\n";
		}
	}
}
namespace sub34{
	void solve(){
		
	}
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	cin >> n >> m;
	if(max(n, m) <= 5000){
		sub12::solve();
	}
	else{
		sub34::solve();
	}
}

Compilation message (stderr)

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:55:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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