oj.uz

Submission #1081428

# Submission time Handle Problem Language Result Execution time Memory
1081428 2024-08-30T04:46:09 Z MinhKien Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 280376 KB 
#include <algorithm>
#include <iostream>
#include <string>

using namespace std;

const int max_child = 16;

struct Trie {
    struct node {
        node *child[max_child];
        int cnt;

        node () {
            fill_n(child, max_child, nullptr);
            cnt = 0;
        }
    };

    node *root;
    Trie () {
        root = new node();
    }

    void add_string(const string &s) {
        node *cur = root;

        int n = s.length();
        for (int i = 0; i < n; ++i) {
            int p = (s[i] - 'A') * 4 + (s[n - i - 1] - 'A');

            if (cur->child[p] == nullptr) cur->child[p] = new node();

            cur = cur->child[p];
            ++cur->cnt;
        }
    }

    void solve(const string &pre, const int n, const string &suf, const int m, int &ans, const int i, node *cur) {
        if (i == max(n, m)) {
            ans += cur->cnt;
            return;
        }

        if (i < min(n, m)) {
            int p = (pre[i] - 'A') * 4 + (suf[i] - 'A');

            if (cur->child[p] == nullptr) return;
            
            solve(pre, n, suf, m, ans, i + 1, cur->child[p]);
        } else {
            if (i < n) {
                for (int j = 0, p = (pre[i] - 'A') * 4; j < 4; ++j, ++p) {
                    if (cur->child[p] != nullptr) {
                        solve(pre, n, suf, m, ans, i + 1, cur->child[p]);
                    }
                }
            } else {
                for (int j = 0, p = suf[i] - 'A'; j < 4; ++j, p += 4) {
                    if (cur->child[p] != nullptr) solve(pre, n, suf, m, ans, i + 1, cur->child[p]);
                }
            }
        }
    }
} T;

int n, q;
string s, pre, suf;

void change (string &s) {
    for (int i = 0; i < s.length(); ++i) {
        if (s[i] == 'C') s[i] = 'B';
        else if (s[i] == 'G') s[i] = 'C';
        else if (s[i] == 'U') s[i] = 'D';
    }
}

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    cin >> n >> q;
    while (n--) {
        cin >> s;
        change(s);
        T.add_string(s);
    }

    while (q--) {
        cin >> pre >> suf;
        change(pre);
        change(suf);
        reverse(suf.begin(), suf.end());
        
        int ans = 0;
        T.solve(pre, pre.length(), suf, suf.length(), ans, 0, T.root);

        cout << ans << "\n";
    }

    return 0;
}

Compilation message

selling_rna.cpp: In function 'void change(std::string&)':
selling_rna.cpp:71:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for (int i = 0; i < s.length(); ++i) {
      |                     ~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1592 ms 280376 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1112 KB Output is correct
2 Correct 16 ms 1492 KB Output is correct
3 Correct 13 ms 1368 KB Output is correct
4 Correct 7 ms 1116 KB Output is correct
5 Correct 19 ms 1372 KB Output is correct
6 Correct 16 ms 1372 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Execution timed out 1592 ms 280376 KB Time limit exceeded
9 Halted 0 ms 0 KB -