oj.uz

Submission #549652

# Submission time Handle Problem Language Result Execution time Memory
549652 2022-04-16T08:22:08 Z colossal_pepe Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 605 ms 1048576 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 400 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 26488 KB Output is correct
2 Correct 168 ms 109360 KB Output is correct
3 Correct 132 ms 74016 KB Output is correct
4 Correct 179 ms 109504 KB Output is correct
5 Correct 85 ms 105772 KB Output is correct
6 Correct 95 ms 105804 KB Output is correct
7 Correct 147 ms 47592 KB Output is correct
8 Correct 119 ms 113404 KB Output is correct
9 Correct 115 ms 113356 KB Output is correct
10 Correct 374 ms 108400 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 605 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 400 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 49 ms 26488 KB Output is correct
9 Correct 168 ms 109360 KB Output is correct
10 Correct 132 ms 74016 KB Output is correct
11 Correct 179 ms 109504 KB Output is correct
12 Correct 85 ms 105772 KB Output is correct
13 Correct 95 ms 105804 KB Output is correct
14 Correct 147 ms 47592 KB Output is correct
15 Correct 119 ms 113404 KB Output is correct
16 Correct 115 ms 113356 KB Output is correct
17 Correct 374 ms 108400 KB Output is correct
18 Runtime error 605 ms 1048576 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -