#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;
int n, m;
vector<pair<string, int>> s_pref, s_suf, pref, suf;
bool compatible(const string& s1, const string& s2) {
if (s1.size() < s2.size()) return 0;
for (int i = 0; i < s2.size(); i++) {
if (s1[i] != s2[i]) return 0;
}
return 1;
}
int bs(int i, int l, bool cat) {
int r = n;
while (r - l > 1) {
int mid = (l + r) / 2;
if (cat) {
if (compatible(s_suf[mid].first, suf[i].first)) l = mid;
else r = mid - 1;
} else {
if (compatible(s_pref[mid].first, pref[i].first)) l = mid;
else r = mid - 1;
}
}
if (cat) {
if (compatible(s_suf[r].first, suf[i].first)) return r;
else if (compatible(s_suf[l].first, suf[i].first)) return l;
} else {
if (compatible(s_pref[r].first, pref[i].first)) return r;
else if (compatible(s_pref[l].first, pref[i].first)) return l;
}
return l - 1;
}
void solvePrefix() {
sort(s_pref.begin(), s_pref.end());
s_pref.push_back({"V", n});
sort(pref.begin(), pref.end());
int l = 0, r;
for (int i = 0; i < m; i++) {
while (s_pref[l].first <= pref[i].first and not compatible(s_pref[l].first, pref[i].first)) l++;
r = bs(i, l, 0);
}
}
void solveSuffix() {
sort(s_suf.begin(), s_suf.end());
s_suf.push_back({"V", n});
sort(suf.begin(), suf.end());
int l = 0, r;
for (int i = 0; i < m; i++) {
while (s_suf[l].first <= suf[i].first and not compatible(s_suf[l].first, suf[i].first)) l++;
r = bs(i, l, 1);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
s_pref.resize(n), s_suf.resize(n), pref.resize(m), suf.resize(m);
for (int i = 0; i < n; i++) {
s_pref[i].second = s_suf[i].second = i;
string s;
cin >> s;
s_pref[i].first = s;
reverse(s.begin(), s.end());
s_suf[i].first = s;
}
for (int i = 0; i < m; i++) {
pref[i].second = suf[i].second = i;
cin >> pref[i].first >> suf[i].first;
reverse(suf[i].first.begin(), suf[i].first.end());
}
solvePrefix();
solveSuffix();
return 0;
}
Compilation message
selling_rna.cpp: In function 'bool compatible(const string&, const string&)':
selling_rna.cpp:12:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
12 | for (int i = 0; i < s2.size(); i++) {
| ~~^~~~~~~~~~~
selling_rna.cpp: In function 'void solvePrefix()':
selling_rna.cpp:44:16: warning: variable 'r' set but not used [-Wunused-but-set-variable]
44 | int l = 0, r;
| ^
selling_rna.cpp: In function 'void solveSuffix()':
selling_rna.cpp:55:16: warning: variable 'r' set but not used [-Wunused-but-set-variable]
55 | int l = 0, r;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
10752 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
68 ms |
10532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
