oj.uz

Submission #938089

# Submission time Handle Problem Language Result Execution time Memory
938089 2024-03-04T19:29:27 Z codefox Selling RNA Strands (JOI16_selling_rna) C++14
60 / 100
 1500 ms 278604 KB 
#include <bits/stdc++.h>

using namespace std;

#pragma GCC optimize("O3")

int N = 3*1e6;

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<vector<int>> pnodes(N);
    vector<vector<int>> snodes(N);

    vector<int> alph(200);
    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]].push_back(i);
        }
        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]].push_back(i);
        }
    }

    for (int i = 0; i < m; i++)
    {
        int p1 = 0;
        int p2 = 0;
        int sol = 0;
        while (p1 < pnodes[pind[i]].size() && p2 < snodes[sind[i]].size())
        {
            if (pnodes[pind[i]][p1] == snodes[sind[i]][p2]) sol++;
            if (pnodes[pind[i]][p1] > snodes[sind[i]][p2]) p2++;
            else p1++;
        }
        cout << sol << "\n";
    }

    return 0;
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:114:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |         while (p1 < pnodes[pind[i]].size() && p2 < snodes[sind[i]].size())
      |                ~~~^~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:114:50: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |         while (p1 < pnodes[pind[i]].size() && p2 < snodes[sind[i]].size())
      |                                               ~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 258644 KB Output is correct
2 Correct 67 ms 258644 KB Output is correct
3 Correct 67 ms 258776 KB Output is correct
4 Correct 66 ms 258644 KB Output is correct
5 Correct 66 ms 258584 KB Output is correct
6 Correct 67 ms 258748 KB Output is correct
7 Correct 70 ms 258640 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 267416 KB Output is correct
2 Correct 129 ms 271872 KB Output is correct
3 Correct 115 ms 269620 KB Output is correct
4 Correct 123 ms 271440 KB Output is correct
5 Correct 84 ms 260692 KB Output is correct
6 Correct 82 ms 260692 KB Output is correct
7 Correct 126 ms 275872 KB Output is correct
8 Correct 102 ms 261204 KB Output is correct
9 Correct 104 ms 261460 KB Output is correct
10 Correct 122 ms 266704 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1449 ms 261456 KB Output is correct
2 Correct 928 ms 260948 KB Output is correct
3 Correct 1468 ms 261828 KB Output is correct
4 Correct 384 ms 261208 KB Output is correct
5 Correct 761 ms 260948 KB Output is correct
6 Correct 1256 ms 261716 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 258644 KB Output is correct
2 Correct 67 ms 258644 KB Output is correct
3 Correct 67 ms 258776 KB Output is correct
4 Correct 66 ms 258644 KB Output is correct
5 Correct 66 ms 258584 KB Output is correct
6 Correct 67 ms 258748 KB Output is correct
7 Correct 70 ms 258640 KB Output is correct
8 Correct 99 ms 267416 KB Output is correct
9 Correct 129 ms 271872 KB Output is correct
10 Correct 115 ms 269620 KB Output is correct
11 Correct 123 ms 271440 KB Output is correct
12 Correct 84 ms 260692 KB Output is correct
13 Correct 82 ms 260692 KB Output is correct
14 Correct 126 ms 275872 KB Output is correct
15 Correct 102 ms 261204 KB Output is correct
16 Correct 104 ms 261460 KB Output is correct
17 Correct 122 ms 266704 KB Output is correct
18 Correct 1449 ms 261456 KB Output is correct
19 Correct 928 ms 260948 KB Output is correct
20 Correct 1468 ms 261828 KB Output is correct
21 Correct 384 ms 261208 KB Output is correct
22 Correct 761 ms 260948 KB Output is correct
23 Correct 1256 ms 261716 KB Output is correct
24 Correct 401 ms 272468 KB Output is correct
25 Correct 1010 ms 269900 KB Output is correct
26 Correct 227 ms 275412 KB Output is correct
27 Correct 340 ms 272536 KB Output is correct
28 Execution timed out 1546 ms 278604 KB Time limit exceeded
29 Halted 0 ms 0 KB -