Submission #549655

#	Time	Username	Problem	Language	Result	Execution time	Memory
549655		colossal_pepe	Selling RNA Strands (JOI16_selling_rna)	C++17	0 / 100	68 ms	10752 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;

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 (stderr)

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;
      |                ^

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