oj.uz

Submission #419013

# Submission time Handle Problem Language Result Execution time Memory
419013 2021-06-06T10:34:51 Z cpp219 Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1500 ms 433012 KB 
#pragma GCC optimization "O2"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")

#include <bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 2e6 + 9;
const ll mod = 1e9;
typedef pair<ll,ll> LL;
string s;
ll n,Q;

char Convert(char c){
    if (c == 'A') return '0';
    if (c == 'G') return '1';
    if (c == 'C') return '2';
    if (c == 'U') return '3';
}

void oper(string &s){
    for (ll j = 0;j < s.size();j++) s[j] = Convert(s[j]);
}

struct Trie{
    Trie *child[5][5];
    ll cnt = 0;
    Trie(){
        cnt = 0;
        for (ll i = 0;i < 5;i++)
            for (ll j = 0;j < 5;j++) child[i][j] = NULL;
    }
    void Add(ll id,string &s){
        cnt++;
        if (id == s.size()) return;
        ll sz = s.size();
        ll x = s[id] - '0',y = s[sz - id - 1] - '0';
        if (!child[x][y]) child[x][y] = new Trie;
        child[x][y] -> Add(id + 1,s);
    }
    ll Get(ll id,string &pre,string &suf){
        /// pre.sz == suf.sz;
        if (id == pre.size()) return cnt;
        ll sz = suf.size(),ans = 0;
        ll x = pre[id] - '0',y = suf[sz - id - 1] - '0';
        if (x == 4){
            for (ll i = 0;i < 4;i++) if (child[i][y])
                ans += child[i][y] -> Get(id + 1,pre,suf);
        }
        else if (y == 4){
            for (ll i = 0;i < 4;i++) if (child[x][i])
                ans += child[x][i] -> Get(id + 1,pre,suf);
        }
        else{
            if (child[x][y]) ans += child[x][y] -> Get(id + 1,pre,suf);
        }
        return ans;
    }
};
string p,q;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define task "tst"
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        //freopen(task".out", "w", stdout);
    }
    Trie Tree;
    cin>>n>>Q;
    for (ll i = 1;i <= n;i++){
        cin>>s; oper(s);
        Tree.Add(0,s);
    }
    while(Q--){
        cin>>p>>q; oper(p); oper(q);
        string now;
        while(p.size() < q.size()) p = p + '4';
        while(q.size() + now.size() < p.size()) now += '4';
        now += q;
        cout<<Tree.Get(0,p,now)<<"\n";
    }
}

Compilation message

selling_rna.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    1 | #pragma GCC optimization "O2"
      | 
selling_rna.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      | 
selling_rna.cpp: In function 'void oper(std::string&)':
selling_rna.cpp:25:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for (ll j = 0;j < s.size();j++) s[j] = Convert(s[j]);
      |                   ~~^~~~~~~~~~
selling_rna.cpp: In member function 'void Trie::Add(int, std::string&)':
selling_rna.cpp:38:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         if (id == s.size()) return;
      |             ~~~^~~~~~~~~~~
selling_rna.cpp: In member function 'int Trie::Get(int, std::string&, std::string&)':
selling_rna.cpp:46:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         if (id == pre.size()) return cnt;
      |             ~~~^~~~~~~~~~~~~
selling_rna.cpp: In function 'char Convert(char)':
selling_rna.cpp:22:1: warning: control reaches end of non-void function [-Wreturn-type]
   22 | }
      | ^
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:69:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1589 ms 433012 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 972 KB Output is correct
2 Correct 45 ms 1736 KB Output is correct
3 Correct 27 ms 1356 KB Output is correct
4 Correct 14 ms 864 KB Output is correct
5 Correct 32 ms 1736 KB Output is correct
6 Correct 25 ms 1432 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Execution timed out 1589 ms 433012 KB Time limit exceeded
9 Halted 0 ms 0 KB -