Submission #549652

#	Time	Username	Problem	Language	Result	Execution time	Memory
549652		colossal_pepe	Selling RNA Strands (JOI16_selling_rna)	C++17	35 / 100	605 ms	1048576 KiB

selling_rna

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;

int n, m;
vector<pair<string, int>> s_pref, s_suf, pref, suf;
vector<vector<int>> ans;

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);
        // cout << pref[i].first << " : ";
        for (int j = l; j <= r; j++) {
            // cout << s_pref[j].first << ' ';
            ans[pref[i].second][s_pref[j].second]++;
        }
        // cout << '\n';
    }
}

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);
        // cout << suf[i].first << " : ";
        for (int j = l; j <= r; j++) {
            // cout << s_suf[j].first << ' ';
            ans[suf[i].second][s_suf[j].second]++;
        }
        // cout << '\n';
    }
}

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();
    for (int i = 0; i < m; i++) {
        int cnt = 0;
        for (int j = 0; j < n; j++) {
            if (ans[i][j] == 2) cnt++;
        }
        cout << cnt << '\n';
    }
    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'bool compatible(const string&, const string&)':
selling_rna.cpp:13:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for (int i = 0; i < s2.size(); i++) {
      |                     ~~^~~~~~~~~~~

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