oj.uz

Submission #682064

# Submission time Handle Problem Language Result Execution time Memory
682064 2023-01-15T14:43:30 Z Pannda Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 798 ms 1048576 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = (int)1e5;

struct Trie {
    vector<array<int, 4>> trie;
    vector<bitset<N>> bs;

    Trie() : trie(1), bs(1) {}

    void add(int u, string &s, int i) {
        for (auto c : s) {
            if (!trie[u][c]) {
                trie[u][c] = trie.size();
                trie.push_back({});
                bs.push_back(bitset<N>());
            }
            u = trie[u][c];
            bs[u].set(i);
        }
    }

    int get(int u, string &s) {
        for (auto c : s) {
            if (!trie[u][c]) {
                return 0;
            }
            u = trie[u][c];
        }
        return u;
    }
};

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

    int n, q;
    cin >> n >> q;
    Trie pref, suff;

    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (auto &ch : s) {
            if (ch == 'A') ch = 0;
            if (ch == 'G') ch = 1;
            if (ch == 'C') ch = 2;
            if (ch == 'U') ch = 3;
        }
        pref.add(0, s, i);
        reverse(s.begin(), s.end());
        suff.add(0, s, i);
    }

    while (q--) {
        string p, s;
        cin >> p >> s;
        reverse(s.begin(), s.end());

        for (auto &ch : p) {
            if (ch == 'A') ch = 0;
            if (ch == 'G') ch = 1;
            if (ch == 'C') ch = 2;
            if (ch == 'U') ch = 3;
        }

        for (auto &ch : s) {
            if (ch == 'A') ch = 0;
            if (ch == 'G') ch = 1;
            if (ch == 'C') ch = 2;
            if (ch == 'U') ch = 3;
        }

        int pref_id = pref.get(0, p);
        int suff_id = suff.get(0, s);

        bitset<N> key = pref.bs[pref_id] & suff.bs[suff_id];

        cout << key.count() << '\n';
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3488 KB Output is correct
2 Correct 3 ms 3552 KB Output is correct
3 Correct 4 ms 5224 KB Output is correct
4 Correct 3 ms 3124 KB Output is correct
5 Correct 4 ms 3472 KB Output is correct
6 Correct 3 ms 2976 KB Output is correct
7 Correct 3 ms 3540 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 698 ms 1332 KB Output is correct
2 Correct 288 ms 121800 KB Output is correct
3 Correct 234 ms 68396 KB Output is correct
4 Correct 204 ms 1336 KB Output is correct
5 Correct 359 ms 72624 KB Output is correct
6 Correct 427 ms 69000 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3488 KB Output is correct
2 Correct 3 ms 3552 KB Output is correct
3 Correct 4 ms 5224 KB Output is correct
4 Correct 3 ms 3124 KB Output is correct
5 Correct 4 ms 3472 KB Output is correct
6 Correct 3 ms 2976 KB Output is correct
7 Correct 3 ms 3540 KB Output is correct
8 Runtime error 798 ms 1048576 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -