oj.uz

답안 #601814

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
601814 2022-07-22T10:28:24 Z elkernos Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 289 ms 191504 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];
        }
        trie[v].id.emplace_back(i);
    }
    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;
        }
        vector<int> &wek1 = trie.trie[one].id;
        vector<int> &wek2 = trierev.trie[two].id;
        int lo = wek1.front(), hi = wek1.back();
        auto it1 = lower_bound(wek2.begin(), wek2.end(), lo);
        auto it2 = upper_bound(wek2.begin(), wek2.end(), hi);
        if(it1 == wek2.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
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 238 ms 152764 KB Output is correct
2 Correct 231 ms 145324 KB Output is correct
3 Correct 234 ms 151100 KB Output is correct
4 Correct 230 ms 144004 KB Output is correct
5 Correct 271 ms 191504 KB Output is correct
6 Correct 289 ms 191320 KB Output is correct
7 Correct 57 ms 19668 KB Output is correct
8 Correct 238 ms 126740 KB Output is correct
9 Correct 219 ms 113320 KB Output is correct
10 Correct 175 ms 109376 KB Output is correct

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 3940 KB Output is correct
2 Correct 23 ms 3288 KB Output is correct
3 Correct 26 ms 3764 KB Output is correct
4 Correct 17 ms 3224 KB Output is correct
5 Correct 20 ms 3284 KB Output is correct
6 Correct 24 ms 3724 KB Output is correct

Subtask #4
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 238 ms 152764 KB Output is correct
9 Correct 231 ms 145324 KB Output is correct
10 Correct 234 ms 151100 KB Output is correct
11 Correct 230 ms 144004 KB Output is correct
12 Correct 271 ms 191504 KB Output is correct
13 Correct 289 ms 191320 KB Output is correct
14 Correct 57 ms 19668 KB Output is correct
15 Correct 238 ms 126740 KB Output is correct
16 Correct 219 ms 113320 KB Output is correct
17 Correct 175 ms 109376 KB Output is correct
18 Correct 31 ms 3940 KB Output is correct
19 Correct 23 ms 3288 KB Output is correct
20 Correct 26 ms 3764 KB Output is correct
21 Correct 17 ms 3224 KB Output is correct
22 Correct 20 ms 3284 KB Output is correct
23 Correct 24 ms 3724 KB Output is correct
24 Correct 235 ms 127188 KB Output is correct
25 Correct 243 ms 127352 KB Output is correct
26 Correct 236 ms 125888 KB Output is correct
27 Correct 215 ms 125900 KB Output is correct
28 Correct 166 ms 39996 KB Output is correct
29 Correct 75 ms 14944 KB Output is correct