oj.uz

Submission #601804

# Submission time Handle Problem Language Result Execution time Memory
601804 2022-07-22T10:20:55 Z elkernos Selling RNA Strands (JOI16_selling_rna) C++17
0 / 100
 302 ms 156392 KB 
#include <bits/stdc++.h>

using namespace std;

struct T {
    int nxt[4] = {-1, -1, -1, -1};
    vector<int> id;
};

int mapuj(char x)
{
    if(x == 'A') {
        return 0;
    }
    if(x == 'G') {
        return 1;
    }
    if(x == 'C') {
        return 2;
    }
    if(x == 'U') {
        return 3;
    }
}

struct tree {
    vector<T> trie;
    tree() { trie.emplace_back(); }
    void insert(string &s, int i)
    {
        int v = 0;
        for(char x : s) {
            int id = mapuj(x);
            if(trie[v].nxt[id] == -1) {
                trie[v].nxt[id] = (int)trie.size();
                trie.emplace_back();
            }
            trie[v].id.emplace_back(i);
            v = trie[v].nxt[id];
        }
    }
    int search(string &s)
    {
        int v = 0;
        for(char x : s) {
            int id = mapuj(x);
            if(trie[v].nxt[id] == -1) {
                return -1;
            }
            v = trie[v].nxt[id];
        }
        return v;
    }
};

int32_t main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n, q;
    cin >> n >> q;
    vector<string> s(n + 1);
    for(int i = 1; i <= n; i++) {
        cin >> s[i];
    }
    sort(1 + s.begin(), s.end());
    tree trie, trierev;
    for(int i = 1; i <= n; ++i) {
        trie.insert(s[i], i);
        reverse(s[i].begin(), s[i].end());
        trierev.insert(s[i], i);
    }
    for(int i = 1; i <= q; i++) {
        string pre, suf;
        cin >> pre >> suf;
        int one = trie.search(pre);
        reverse(suf.begin(), suf.end());
        int two = trierev.search(suf);
        if(one == -1 || two == -1) {
            cout << 0 << '\n';
            continue;
        }
        int lo = trie.trie[one].id.front(), hi = trie.trie[one].id.back();
        auto it1 = lower_bound(trierev.trie[two].id.begin(), trierev.trie[two].id.end(), lo);
        auto it2 = upper_bound(trierev.trie[two].id.begin(), trierev.trie[two].id.end(), hi);
        if(it1 == trierev.trie[two].id.end() || hi < *it1) {
            cout << 0 << '\n';
            continue;
        }
        cout << distance(it1, it2) << '\n';
    }
}

Compilation message

selling_rna.cpp: In function 'int mapuj(char)':
selling_rna.cpp:24:1: warning: control reaches end of non-void function [-Wreturn-type]
   24 | }
      | ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 302 ms 156392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 6044 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -