Submission #938077

#	Time	Username	Problem	Language	Result	Execution time	Memory
938077		codefox	Selling RNA Strands (JOI16_selling_rna)	C++14	60 / 100	1541 ms	284036 KiB

selling_rna

#include <bits/stdc++.h>

using namespace std;

int N = 3*1e6;

int main()
{
    //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(300);
    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 (stderr)

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

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 0 / 40