Submission #1081439

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081439		MinhKien	Selling RNA Strands (JOI16_selling_rna)	C++17	35 / 100	1533 ms	277072 KiB

selling_rna

#include <iostream>
#include <string>

using namespace std;

const int max_child = 16;

string pre, suf;
int x, y;

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(int &ans, const int i, node *cur) {
        if (i == max(x, y)) {
            ans += cur->cnt;
            return;
        }

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

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

int n, q;
string s;

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);
        x = pre.length();
        y = suf.length();
        
        int ans = 0;
        T.solve(ans, 0, T.root);

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

    return 0;
}

Compilation message (stderr)

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

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