제출 #59627

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59627		FLDutchman	Selling RNA Strands (JOI16_selling_rna)	C++14	35 / 100	1579 ms	611012 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;

#define pb push_back

typedef vector<int> vi;

struct trie{
    vi strings;
    vector<trie*> cld;
    trie(){
        cld.assign(4, 0);
    }
};


int size = 0;

void insert(trie* t, vi &s, int i){
    //cout << i << endl;
    if(i == s.size()){ t->strings.pb(size); return;}
    auto &c = t->cld[s[i]];
    t->strings.pb(size);
    if(!c) c = new trie();
    insert(c, s, i+1);
}

int cnt(trie *t, vi &s, int i, int l, int r){
    if(i == s.size()){
        //cout << "Counting ";
        //for(int k : t->strings) cout << k << " ";
        //cout << endl;
        return lower_bound(t->strings.begin(), t->strings.end(), r) 
             - lower_bound(t->strings.begin(), t->strings.end(), l);
    } else {
        if(!t->cld[s[i]]) return 0;
        return cnt(t->cld[s[i]], s, i+1, l, r);
    }
}

struct modTrie{
    int sz = 0;
    vector<modTrie*> cld;
    int l, r;
    modTrie(){
        cld.assign(16, 0);
    }
};

void insert(modTrie* t, vi &s, int i){
    if(i == s.size()){ t->sz++; return;}
    auto &c = t->cld[s[i]];
    if(!c) c = new modTrie();
    insert(c, s, i+1);
}

trie *T, *revT;

vi S(0), revS(0);
void dfs(modTrie* t){
    t->l = size;
    //cout<<t->sz<<endl;
    for(int i = 0; i < t->sz; i++) {
        insert(T, S, 0);
        insert(revT, revS, 0);
        size++;
    }
    for (int i = 0; i < 16; i++) if(t->cld[i]) {
        S.pb(i%4); revS.pb(i/4);
        dfs(t->cld[i]);
        S.pop_back(); revS.pop_back();
    }
    t->r = size;
}

void getRange(modTrie* t, vi &s, int i, int &l, int &r){
    if(i == s.size()){
        l = t->l;
        r = t->r;
    } else {
        if(!t->cld[s[i]]){
            l = t->l;
            r = t->l;
        } else getRange(t->cld[s[i]], s, i+1, l, r);
    }
}

int val[300];

int N, M;

modTrie* modT;

int main(){
    val['A'] = 0;
    val['G'] = 1;
    val['C'] = 2;
    val['U'] = 3;
    cin >> N >> M;
    modT = new modTrie();
    T = new trie();
    revT = new trie();
    for(int i = 0; i < N; i++){
        string s;
        cin >> s;
        vi S;
        for(int j = 0; j < s.size(); j++){
            S.pb( val[s[j]] + 4*val[s[s.size() - 1 - j ]] );
        }
        //cout << "Made S" << endl;
        insert(modT, S, 0);
    }
    dfs(modT);
    //cout << "Done " << endl;

    for(int i = 0; i < M; i++){
        string p, q;
        cin >> p >> q;
        reverse(q.begin(), q.end());
        vi P, Q, S;
        for(char c : p) P.pb(val[c]);
        for(char c : q) Q.pb(val[c]);
        for(int j = 0; j < min(p.size(), q.size()); j++) S.pb(P[j] + 4*Q[j]);
        int l, r;
        getRange(modT, S, 0, l, r);
        //cout << "Range " << l << " " << r << endl;
        //cout << "lowest sz " << S.size() << endl;
        if(P.size() < Q.size()) {
            cout << cnt(revT, Q, 0, l, r) << endl;
        } else cout << cnt(T, P, 0, l, r) << endl;
    }
}




/*

3 3
AA
AA
AGA


*/

컴파일 시 표준 에러 (stderr) 메시지

selling_rna.cpp: In function 'void insert(trie*, vi&, int)':
selling_rna.cpp:21:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(i == s.size()){ t->strings.pb(size); return;}
        ~~^~~~~~~~~~~
selling_rna.cpp: In function 'int cnt(trie*, vi&, int, int, int)':
selling_rna.cpp:29:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(i == s.size()){
        ~~^~~~~~~~~~~
selling_rna.cpp: In function 'void insert(modTrie*, vi&, int)':
selling_rna.cpp:51:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(i == s.size()){ t->sz++; return;}
        ~~^~~~~~~~~~~
selling_rna.cpp: In function 'void getRange(modTrie*, vi&, int, int&, int&)':
selling_rna.cpp:77:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(i == s.size()){
        ~~^~~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:107:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < s.size(); j++){
                        ~~^~~~~~~~~~
selling_rna.cpp:108:27: warning: array subscript has type 'char' [-Wchar-subscripts]
             S.pb( val[s[j]] + 4*val[s[s.size() - 1 - j ]] );
                           ^
selling_rna.cpp:108:57: warning: array subscript has type 'char' [-Wchar-subscripts]
             S.pb( val[s[j]] + 4*val[s[s.size() - 1 - j ]] );
                                                         ^
selling_rna.cpp:121:35: warning: array subscript has type 'char' [-Wchar-subscripts]
         for(char c : p) P.pb(val[c]);
                                   ^
selling_rna.cpp:122:35: warning: array subscript has type 'char' [-Wchar-subscripts]
         for(char c : q) Q.pb(val[c]);
                                   ^
selling_rna.cpp:123:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < min(p.size(), q.size()); j++) S.pb(P[j] + 4*Q[j]);
                        ~~^~~~~~~~~~~~~~~~~~~~~~~~~

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