oj.uz

Submission #938088

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

using namespace std;

#pragma GCC optimize("Ofast")

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);
    map<string, int> mp;
    map<string, int> ms;
    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:116:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |         while (p1 < pnodes[pind[i]].size() && p2 < snodes[sind[i]].size())
      |                ~~~^~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:116:50: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |         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 105 ms 258692 KB Output is correct
2 Correct 67 ms 258644 KB Output is correct
3 Correct 67 ms 258576 KB Output is correct
4 Correct 66 ms 258636 KB Output is correct
5 Correct 68 ms 258644 KB Output is correct
6 Correct 70 ms 258612 KB Output is correct
7 Correct 72 ms 258720 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 267344 KB Output is correct
2 Correct 128 ms 271696 KB Output is correct
3 Correct 116 ms 269532 KB Output is correct
4 Correct 127 ms 271312 KB Output is correct
5 Correct 85 ms 260548 KB Output is correct
6 Correct 82 ms 260688 KB Output is correct
7 Correct 149 ms 276004 KB Output is correct
8 Correct 100 ms 261204 KB Output is correct
9 Correct 102 ms 261200 KB Output is correct
10 Correct 124 ms 266740 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1390 ms 261460 KB Output is correct
2 Correct 899 ms 260692 KB Output is correct
3 Correct 1447 ms 261368 KB Output is correct
4 Correct 480 ms 260712 KB Output is correct
5 Correct 775 ms 260692 KB Output is correct
6 Correct 1266 ms 261520 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 258692 KB Output is correct
2 Correct 67 ms 258644 KB Output is correct
3 Correct 67 ms 258576 KB Output is correct
4 Correct 66 ms 258636 KB Output is correct
5 Correct 68 ms 258644 KB Output is correct
6 Correct 70 ms 258612 KB Output is correct
7 Correct 72 ms 258720 KB Output is correct
8 Correct 104 ms 267344 KB Output is correct
9 Correct 128 ms 271696 KB Output is correct
10 Correct 116 ms 269532 KB Output is correct
11 Correct 127 ms 271312 KB Output is correct
12 Correct 85 ms 260548 KB Output is correct
13 Correct 82 ms 260688 KB Output is correct
14 Correct 149 ms 276004 KB Output is correct
15 Correct 100 ms 261204 KB Output is correct
16 Correct 102 ms 261200 KB Output is correct
17 Correct 124 ms 266740 KB Output is correct
18 Correct 1390 ms 261460 KB Output is correct
19 Correct 899 ms 260692 KB Output is correct
20 Correct 1447 ms 261368 KB Output is correct
21 Correct 480 ms 260712 KB Output is correct
22 Correct 775 ms 260692 KB Output is correct
23 Correct 1266 ms 261520 KB Output is correct
24 Correct 398 ms 269396 KB Output is correct
25 Correct 986 ms 266064 KB Output is correct
26 Correct 234 ms 272308 KB Output is correct
27 Correct 340 ms 269148 KB Output is correct
28 Execution timed out 1541 ms 274856 KB Time limit exceeded
29 Halted 0 ms 0 KB -