oj.uz

Submission #938090

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

using namespace std;

#pragma GCC optimize("O2")

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 78 ms 258640 KB Output is correct
2 Correct 70 ms 258740 KB Output is correct
3 Correct 72 ms 258640 KB Output is correct
4 Correct 76 ms 258900 KB Output is correct
5 Correct 72 ms 258688 KB Output is correct
6 Correct 72 ms 258644 KB Output is correct
7 Correct 71 ms 258644 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 270672 KB Output is correct
2 Correct 126 ms 275024 KB Output is correct
3 Correct 118 ms 272980 KB Output is correct
4 Correct 136 ms 274584 KB Output is correct
5 Correct 91 ms 262860 KB Output is correct
6 Correct 84 ms 263036 KB Output is correct
7 Correct 129 ms 280644 KB Output is correct
8 Correct 105 ms 265788 KB Output is correct
9 Correct 104 ms 265840 KB Output is correct
10 Correct 126 ms 269908 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1235 ms 262264 KB Output is correct
2 Correct 845 ms 261340 KB Output is correct
3 Correct 1330 ms 261408 KB Output is correct
4 Correct 334 ms 260460 KB Output is correct
5 Correct 820 ms 260792 KB Output is correct
6 Correct 1332 ms 261368 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 258640 KB Output is correct
2 Correct 70 ms 258740 KB Output is correct
3 Correct 72 ms 258640 KB Output is correct
4 Correct 76 ms 258900 KB Output is correct
5 Correct 72 ms 258688 KB Output is correct
6 Correct 72 ms 258644 KB Output is correct
7 Correct 71 ms 258644 KB Output is correct
8 Correct 102 ms 270672 KB Output is correct
9 Correct 126 ms 275024 KB Output is correct
10 Correct 118 ms 272980 KB Output is correct
11 Correct 136 ms 274584 KB Output is correct
12 Correct 91 ms 262860 KB Output is correct
13 Correct 84 ms 263036 KB Output is correct
14 Correct 129 ms 280644 KB Output is correct
15 Correct 105 ms 265788 KB Output is correct
16 Correct 104 ms 265840 KB Output is correct
17 Correct 126 ms 269908 KB Output is correct
18 Correct 1235 ms 262264 KB Output is correct
19 Correct 845 ms 261340 KB Output is correct
20 Correct 1330 ms 261408 KB Output is correct
21 Correct 334 ms 260460 KB Output is correct
22 Correct 820 ms 260792 KB Output is correct
23 Correct 1332 ms 261368 KB Output is correct
24 Correct 369 ms 269108 KB Output is correct
25 Correct 881 ms 265928 KB Output is correct
26 Correct 216 ms 271956 KB Output is correct
27 Correct 356 ms 269056 KB Output is correct
28 Execution timed out 1581 ms 274972 KB Time limit exceeded
29 Halted 0 ms 0 KB -