oj.uz

Submission #938125

# Submission time Handle Problem Language Result Execution time Memory
938125 2024-03-04T20:56:32 Z codefox Selling RNA Strands (JOI16_selling_rna) C++14
0 / 100
 69 ms 191824 KB 
#include <bits/stdc++.h>

using namespace std;

#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("popcnt")

int N = 2*1e6+1;

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<int> alph(100);
    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];
    }

    vector<bitset<100000>> pnodes(dp+1);
    vector<bitset<100000>> snodes(ds+1);
    vector<vector<int>> p2nodes(N);
    vector<vector<int>> s2nodes(N);


    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]][i] = 1;
        }
        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]][i] = 1;
        }
    }

    for (int i = 0; i < m; i++)
    {
        int sol =  (snodes[sind[i]]&pnodes[pind[i]]).count();
    }

    return 0;
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:115:13: warning: unused variable 'sol' [-Wunused-variable]
  115 |         int sol =  (snodes[sind[i]]&pnodes[pind[i]]).count();
      |             ^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 173604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 191824 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 174672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 173604 KB Output isn't correct
2 Halted 0 ms 0 KB -