Submission #1111666

#TimeUsernameProblemLanguageResultExecution timeMemory
1111666Zero_OPSelling RNA Strands (JOI16_selling_rna)C++14
35 / 100
1586 ms478616 KiB
#include <bits/stdc++.h> using namespace std; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); int random(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); } const int MAX = 1e5 + 5; const int mod = 1e9 + random(7, 200); const int base = 37; int pw_base[MAX]; void preprocess(){ pw_base[0] = 1; for(int i = 1; i < MAX; ++i){ pw_base[i] = 1LL * pw_base[i - 1] * base % mod; } } int code(char c){ if(c == 'A') return 3; if(c == 'G') return 7; if(c == 'C') return 17; if(c == 'U') return 23; assert(false); } int get_hash(const string& s){ int h = 0; for(auto c : s) h = (1LL * h * base + code(c)) % mod; return h; } int get_hash(const string& s, int l, int r){ int h = 0; for(int i = l; i <= r; ++i) h = (1LL * h * base + code(s[i])) % mod; return h;; } int get_hash(const vector<int>& h, int l, int r){ ++r; int cur = h[r] - (1LL * h[l] * pw_base[r - l]) % mod; if(cur < 0) cur += mod; return cur; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); if(fopen("task.inp", "r")){ freopen("task.inp", "r", stdin); freopen("task.out", "w", stdout); } preprocess(); int N, Q; cin >> N >> Q; vector<string> s(N); vector<int> sz(N); for(int i = 0; i < N; ++i) cin >> s[i], sz[i] = (int)s[i].size(); vector<vector<int>> pref_hash(N); for(int i = 0; i < N; ++i){ pref_hash[i].emplace_back(0); for(auto c : s[i]){ pref_hash[i].emplace_back((1ll * pref_hash[i].back() * base + code(c)) % mod); } } const int B = 250; vector<int> vPref, vSuff; for(int i = 0; i < N; ++i){ for(int j = 1; j <= min(sz[i], B); ++j){ vPref.push_back(get_hash(pref_hash[i], 0, j - 1)); vSuff.push_back(get_hash(pref_hash[i], sz[i] - j, sz[i] - 1)); } } sort(vPref.begin(), vPref.end()); vPref.erase(unique(vPref.begin(), vPref.end()), vPref.end()); sort(vSuff.begin(), vSuff.end()); vSuff.erase(unique(vSuff.begin(), vSuff.end()), vSuff.end()); int vl = (int)vPref.size(); vector<vector<int>> cnt(vl); vector<int> x, y; for(int i = 0; i < N; ++i){ x.clear(); y.clear(); for(int j = 0; j < min(B, sz[i]); ++j){ int h1 = get_hash(pref_hash[i], 0, j); int p1 = lower_bound(vPref.begin(), vPref.end(), h1) - vPref.begin(); x.push_back(p1); int h2 = get_hash(pref_hash[i], sz[i] - j - 1, sz[i] - 1); y.push_back(h2); } for(auto u : x){ for(auto v : y){ cnt[u].emplace_back(v); } } } for(int i = 0; i < vl; ++i){ sort(cnt[i].begin(), cnt[i].end()); } for(int _ = 0; _ < Q; ++_){ string p, q; cin >> p >> q; if((int)p.size() <= B && (int)q.size() <= B){ int hash_p = get_hash(p), hash_q = get_hash(q); if(!binary_search(vPref.begin(), vPref.end(), hash_p)){ cout << 0 << '\n'; continue; } int x = lower_bound(vPref.begin(), vPref.end(), hash_p) - vPref.begin(); int res = upper_bound(cnt[x].begin(), cnt[x].end(), hash_q) - lower_bound(cnt[x].begin(), cnt[x].end(), hash_q); cout << res << '\n'; } else{ int cnt = 0, demand = max((int)p.size(), (int)q.size()), dl = (int)p.size(), dr = (int)q.size(); int hash_p = get_hash(p), hash_q = get_hash(q); for(int i = 0; i < N; ++i){ if(sz[i] >= demand){ if(get_hash(pref_hash[i], 0, dl - 1) == hash_p && get_hash(pref_hash[i], sz[i] - dr, sz[i] - 1) == hash_q){ ++cnt; } } } cout << cnt << '\n'; } } return 0; }

Compilation message (stderr)

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         freopen("task.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:55:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         freopen("task.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...