| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 549654 | colossal_pepe | Selling RNA Strands (JOI16_selling_rna) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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), ans.resize(m, vector<int>(n, 0));
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;
}