oj.uz

Submission #549656

# Submission time Handle Problem Language Result Execution time Memory
549656 2022-04-16T08:30:03 Z colossal_pepe Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 357 ms 113416 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 << " : ";
        if (n > 5000 or m > 5000) continue;
        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 << " : ";
        if (n > 5000 or m > 5000) continue;
        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);
    if (n <= 5000 and m <= 5000) 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 320 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 1 ms 320 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 22544 KB Output is correct
2 Correct 187 ms 109336 KB Output is correct
3 Correct 126 ms 74016 KB Output is correct
4 Correct 183 ms 109328 KB Output is correct
5 Correct 84 ms 105736 KB Output is correct
6 Correct 79 ms 105804 KB Output is correct
7 Correct 151 ms 47524 KB Output is correct
8 Correct 118 ms 113416 KB Output is correct
9 Correct 112 ms 113356 KB Output is correct
10 Correct 357 ms 108432 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 71 ms 16352 KB Execution killed with signal 11
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 320 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 49 ms 22544 KB Output is correct
9 Correct 187 ms 109336 KB Output is correct
10 Correct 126 ms 74016 KB Output is correct
11 Correct 183 ms 109328 KB Output is correct
12 Correct 84 ms 105736 KB Output is correct
13 Correct 79 ms 105804 KB Output is correct
14 Correct 151 ms 47524 KB Output is correct
15 Correct 118 ms 113416 KB Output is correct
16 Correct 112 ms 113356 KB Output is correct
17 Correct 357 ms 108432 KB Output is correct
18 Runtime error 71 ms 16352 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -