제출 #59627

#제출 시각아이디문제언어결과실행 시간메모리
59627FLDutchmanSelling RNA Strands (JOI16_selling_rna)C++14
35 / 100
1579 ms611012 KiB
#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]);
                        ~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...