oj.uz

Submission #938082

# Submission time Handle Problem Language Result Execution time Memory
938082 2024-03-04T19:24:49 Z codefox Selling RNA Strands (JOI16_selling_rna) C++14
60 / 100
 1500 ms 278352 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());

        if (mp[a]==0) 
        {
            pind[i] = ++dp;
            mp[a] = dp;
            int curr = 0;
            for (char c:a)
            {
                int next = alph[c];
                if (prefix[curr][next]==-1)
                {
                    prefix[curr][next] = ++cp;
                }   
                curr = prefix[curr][next];
            }
            preind[curr] = dp;
        }
        else pind[i] = mp[a];
        
        if (ms[b]==0) 
        {
            sind[i] = ++ds;
            ms[b] = ds;
            int curr = 0;
            for (char c:b)
            {
                int next = alph[c];
                if (suffix[curr][next]==-1)
                {
                    suffix[curr][next] = ++cs;
                }   
                curr = suffix[curr][next];
            }
            sufind[curr] = ds;
        }
        else sind[i] = ms[b];
    }


    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:117:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |         while (p1 < pnodes[pind[i]].size() && p2 < snodes[sind[i]].size())
      |                ~~~^~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:117:50: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |         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 112 ms 258744 KB Output is correct
2 Correct 68 ms 258644 KB Output is correct
3 Correct 71 ms 258876 KB Output is correct
4 Correct 73 ms 258568 KB Output is correct
5 Correct 68 ms 258656 KB Output is correct
6 Correct 66 ms 258760 KB Output is correct
7 Correct 66 ms 258640 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 268988 KB Output is correct
2 Correct 130 ms 272208 KB Output is correct
3 Correct 114 ms 270672 KB Output is correct
4 Correct 123 ms 272124 KB Output is correct
5 Correct 90 ms 262760 KB Output is correct
6 Correct 90 ms 262748 KB Output is correct
7 Correct 124 ms 278352 KB Output is correct
8 Correct 105 ms 264020 KB Output is correct
9 Correct 109 ms 265072 KB Output is correct
10 Correct 118 ms 266716 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1255 ms 261648 KB Output is correct
2 Correct 913 ms 260692 KB Output is correct
3 Correct 1470 ms 261272 KB Output is correct
4 Correct 347 ms 260424 KB Output is correct
5 Correct 816 ms 260688 KB Output is correct
6 Correct 1346 ms 261300 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 258744 KB Output is correct
2 Correct 68 ms 258644 KB Output is correct
3 Correct 71 ms 258876 KB Output is correct
4 Correct 73 ms 258568 KB Output is correct
5 Correct 68 ms 258656 KB Output is correct
6 Correct 66 ms 258760 KB Output is correct
7 Correct 66 ms 258640 KB Output is correct
8 Correct 108 ms 268988 KB Output is correct
9 Correct 130 ms 272208 KB Output is correct
10 Correct 114 ms 270672 KB Output is correct
11 Correct 123 ms 272124 KB Output is correct
12 Correct 90 ms 262760 KB Output is correct
13 Correct 90 ms 262748 KB Output is correct
14 Correct 124 ms 278352 KB Output is correct
15 Correct 105 ms 264020 KB Output is correct
16 Correct 109 ms 265072 KB Output is correct
17 Correct 118 ms 266716 KB Output is correct
18 Correct 1255 ms 261648 KB Output is correct
19 Correct 913 ms 260692 KB Output is correct
20 Correct 1470 ms 261272 KB Output is correct
21 Correct 347 ms 260424 KB Output is correct
22 Correct 816 ms 260688 KB Output is correct
23 Correct 1346 ms 261300 KB Output is correct
24 Correct 434 ms 269140 KB Output is correct
25 Correct 1032 ms 265808 KB Output is correct
26 Correct 215 ms 272468 KB Output is correct
27 Correct 361 ms 269412 KB Output is correct
28 Execution timed out 1540 ms 274652 KB Time limit exceeded
29 Halted 0 ms 0 KB -