oj.uz

Submission #938118

# Submission time Handle Problem Language Result Execution time Memory
938118 2024-03-04T20:31:16 Z codefox Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 385 ms 1048576 KB 
#include <bits/stdc++.h>

using namespace std;

#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("popcnt")

int N = 2*1e6+1;

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

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    int n, m;
    cin >> n >> m;

    vector<array<int, 4>> prefix(N, {-1, -1, -1, -1});
    vector<array<int, 4>> suffix(N, {-1, -1, -1, -1});
    vector<int> preind(N, -1);
    vector<int> sufind(N, -1);

    vector<bitset<100000>> pnodes(n);
    vector<bitset<100000>> snodes(n);

    vector<int> alph(100);
    alph['A'] = 0;
    alph['C'] = 1;
    alph['G'] = 2;
    alph['U'] = 3; 

    vector<string> ns(n);
    vector<int> pind(m);
    vector<int> sind(m);
    int cp = 0;
    int cs = 0;
    int dp = 0;
    int ds = 0;

    for (int i = 0; i < n; i++) cin >> ns[i];

    for (int i = 0; i < m; i++)
    {
        string a, b;
        cin >> a >> b;
        reverse(b.begin(), b.end());

        int curr = 0;
        for (char c:a)
        {
            int next = alph[c];
            if (prefix[curr][next]==-1)
            {
                prefix[curr][next] = ++cp;
            }   
            curr = prefix[curr][next];
        }
        if (preind[curr]==-1) 
        {
            preind[curr] = ++dp;
            pind[i] = dp;
        }
        else pind[i] = preind[curr];
        

        curr = 0;
        for (char c:b)
        {
            int next = alph[c];
            if (suffix[curr][next]==-1)
            {
                suffix[curr][next] = ++cs;
            }   
            curr = suffix[curr][next];
        }
        if (sufind[curr] ==-1) 
        {
            sufind[curr] = ++ds;
            sind[i] = ds;
        }
        else sind[i] =sufind[curr];
    }


    for (int i = 0; i < n; i++)
    {
        int curr = 0;
        for (char c:ns[i])
        {
            int next = alph[c];
            curr = prefix[curr][next];
            if (curr == -1) break;
            if (preind[curr]!=-1) pnodes[preind[curr]][i] = 1;
        }
        reverse(ns[i].begin(), ns[i].end());
        curr = 0;
        for (char c:ns[i])
        {
            int next = alph[c];
            curr = suffix[curr][next];
            if (curr == -1) break;
            if (sufind[curr]!=-1)  snodes[sufind[curr]][i] = 1;
        }
    }

    for (int i = 0; i < m; i++)
    {
        cout << (snodes[sind[i]]&pnodes[pind[i]]).count() << "\n";
    }

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 80984 KB Output is correct
2 Correct 14 ms 80988 KB Output is correct
3 Correct 18 ms 80980 KB Output is correct
4 Correct 14 ms 80984 KB Output is correct
5 Correct 19 ms 80984 KB Output is correct
6 Correct 14 ms 80988 KB Output is correct
7 Correct 14 ms 80988 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 129876 KB Output is correct
2 Correct 74 ms 203348 KB Output is correct
3 Correct 55 ms 159328 KB Output is correct
4 Correct 69 ms 203396 KB Output is correct
5 Correct 67 ms 202444 KB Output is correct
6 Correct 65 ms 202576 KB Output is correct
7 Correct 64 ms 122788 KB Output is correct
8 Correct 81 ms 203344 KB Output is correct
9 Correct 83 ms 203344 KB Output is correct
10 Correct 63 ms 203220 KB Output is correct

Subtask #3
0 / 25.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 80984 KB Output is correct
2 Correct 14 ms 80988 KB Output is correct
3 Correct 18 ms 80980 KB Output is correct
4 Correct 14 ms 80984 KB Output is correct
5 Correct 19 ms 80984 KB Output is correct
6 Correct 14 ms 80988 KB Output is correct
7 Correct 14 ms 80988 KB Output is correct
8 Correct 56 ms 129876 KB Output is correct
9 Correct 74 ms 203348 KB Output is correct
10 Correct 55 ms 159328 KB Output is correct
11 Correct 69 ms 203396 KB Output is correct
12 Correct 67 ms 202444 KB Output is correct
13 Correct 65 ms 202576 KB Output is correct
14 Correct 64 ms 122788 KB Output is correct
15 Correct 81 ms 203344 KB Output is correct
16 Correct 83 ms 203344 KB Output is correct
17 Correct 63 ms 203220 KB Output is correct
18 Runtime error 385 ms 1048576 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -