oj.uz

Submission #938123

# Submission time Handle Problem Language Result Execution time Memory
938123 2024-03-04T20:52:48 Z codefox Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 394 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<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];
    }

    vector<bitset<80000>> pnodes(m);
    vector<bitset<80000>> snodes(m);
    vector<vector<int>> p2nodes(N);
    vector<vector<int>> s2nodes(N);


    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++)
    {
        int sol =  (snodes[sind[i]]&pnodes[pind[i]]).count();
        int p1 = 0;
        int p2 = 0;
        int pi = pind[i];
        int si = sind[i];
        while (p1 < p2nodes[pi].size() && p2 < s2nodes[si].size())
        {
            if (p2nodes[pi][p1] == s2nodes[si][p2]) 
            {
                p1++;
                p2++;
                sol++;
            }
            else if (p2nodes[pi][p1] > s2nodes[si][p2]) p2++;
            else p1++;
        }
        cout << sol << "\n";
    }

    return 0;
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:120:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |         while (p1 < p2nodes[pi].size() && p2 < s2nodes[si].size())
      |                ~~~^~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:120:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |         while (p1 < p2nodes[pi].size() && p2 < s2nodes[si].size())
      |                                           ~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 174664 KB Output is correct
2 Correct 38 ms 174416 KB Output is correct
3 Correct 39 ms 174420 KB Output is correct
4 Correct 38 ms 174440 KB Output is correct
5 Correct 39 ms 174420 KB Output is correct
6 Correct 37 ms 174428 KB Output is correct
7 Correct 42 ms 174424 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 216348 KB Output is correct
2 Correct 103 ms 275000 KB Output is correct
3 Correct 115 ms 274952 KB Output is correct
4 Correct 107 ms 274916 KB Output is correct
5 Correct 99 ms 273280 KB Output is correct
6 Correct 98 ms 273364 KB Output is correct
7 Correct 113 ms 275540 KB Output is correct
8 Correct 123 ms 276356 KB Output is correct
9 Correct 122 ms 276048 KB Output is correct
10 Correct 103 ms 274756 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 394 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 69 ms 174664 KB Output is correct
2 Correct 38 ms 174416 KB Output is correct
3 Correct 39 ms 174420 KB Output is correct
4 Correct 38 ms 174440 KB Output is correct
5 Correct 39 ms 174420 KB Output is correct
6 Correct 37 ms 174428 KB Output is correct
7 Correct 42 ms 174424 KB Output is correct
8 Correct 85 ms 216348 KB Output is correct
9 Correct 103 ms 275000 KB Output is correct
10 Correct 115 ms 274952 KB Output is correct
11 Correct 107 ms 274916 KB Output is correct
12 Correct 99 ms 273280 KB Output is correct
13 Correct 98 ms 273364 KB Output is correct
14 Correct 113 ms 275540 KB Output is correct
15 Correct 123 ms 276356 KB Output is correct
16 Correct 122 ms 276048 KB Output is correct
17 Correct 103 ms 274756 KB Output is correct
18 Runtime error 394 ms 1048576 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -