제출 #1279336

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1279336		MinhKien	Selling RNA Strands (JOI16_selling_rna)	C++17	35 / 100	1599 ms	133752 KiB

selling_rna

#include <iostream>
#include <string>

using namespace std;

const int M = 2e6 + 10;
const int C = 16;

int n, m, x, y;
string s, pre, suf;

struct Trie {
    struct node {
        int child[C], cnt;

        node () {
            fill_n(child, C, -1);
        }
    } nd[M];

    int root, cnt;
    Trie () {
        root = cnt = 0;
    }

    void NewNode(int u, int c) {
        nd[u].child[c] = ++cnt;
    }

    void add() {
        int cur = root, kk = s.size();
        for (int i = 0; i < kk; ++i) {
            int c = (s[i] - 'A') << 2 | (s[kk - i - 1] - 'A');
            if (nd[cur].child[c] == -1) NewNode(cur, c);
            cur = nd[cur].child[c];
            ++nd[cur].cnt;
        }
    }

    void calc(int i, int cur, int &ans) {
        if (cur == -1) return;
        if (i == max(x, y)) {
            ans += nd[cur].cnt;
            return;
        }

        if (i < min(x, y)) {
            int c = (pre[i] - 'A') << 2 | (suf[y - i - 1] - 'A');
            calc(i + 1, nd[cur].child[c], ans);
        } else {
            if (i < x) {
                int Fix = (pre[i] - 'A') << 2;
                for (int j = 0; j < 4; ++j) {
                    calc(i + 1, nd[cur].child[Fix + j], ans);
                }
            } else {
                int Fix = suf[y - i - 1] - 'A';
                for (int j = 0; j <= 12; j += 4) {
                    calc(i + 1, nd[cur].child[j + Fix], ans);
                }
            }
        }
    }
} T;

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

int main() {
    //freopen("input.txt", "r", stdin);

    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> n >> m;
    while (n--) {
        cin >> s;
        change(s);
        T.add();
    }

    while (m--) {
        cin >> pre >> suf;
        x = pre.size(); y = suf.size();
        change(pre); change(suf);

        int ans = 0;
        T.calc(0, 0, ans);
        cout << ans << "\n";
    }

    return 0;
}

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