제출 #290392

#제출 시각아이디문제언어결과실행 시간메모리
290392alexandra_udristoiuSelling RNA Strands (JOI16_selling_rna)C++14
100 / 100
537 ms223896 KiB
#include<iostream> #include<cstring> #include<vector> #include<algorithm> #define DIM 100005 using namespace std; int n, m, k, i, j, u, ii; int ind[DIM], sol[DIM]; char p[DIM], q[DIM]; vector<char> v[DIM], c[DIM]; struct str{ int p, u, ind; }; str w[DIM]; struct trie1{ int minim, maxim; trie1 *f[5]; trie1(){ minim = 10000000; maxim = 0; f[4] = f[1] = f[2] = f[3] = NULL; } }; trie1 *r1; struct trie2{ vector<int> v; trie2 *f[5]; trie2(){ f[4] = f[1] = f[2] = f[3] = NULL; } }; trie2 *r2; void read(char s[]){ cin>> s; k = strlen(s); for(int i = 0; i < k; i++){ if(s[i] == 'A'){ s[i] = 1; } if(s[i] == 'C'){ s[i] = 2; } if(s[i] == 'G'){ s[i] = 3; } if(s[i] == 'U'){ s[i] = 4; } } } int cmp2(str a, str b){ return a.p > b.p; } int cmp(int a, int b){ for(int i = 0; i < min(v[a].size(), v[b].size() ); i++){ if(v[a][i] != v[b][i]){ return v[a][i] < v[b][i]; } } return v[a].size() < v[b].size(); } void adauga1(trie1 *r, char *s, int ind){ r->minim = min(r->minim, ind); r->maxim = max(r->maxim, ind); if(*s != 0){ if(r->f[*s] == NULL){ r->f[*s] = new trie1; } adauga1(r->f[*s], s + 1, ind); } } void query1(trie1 *r, char *s, str &w){ if(*s == 0){ w.p = r->minim; w.u = r->maxim; } else{ if(r->f[*s] != NULL){ query1(r->f[*s], s + 1, w); } } } void adauga2(trie2 *r, char *s, int ind){ r->v.push_back(ind); if(*s != 0){ if(r->f[*s] == NULL){ r->f[*s] = new trie2; } adauga2(r->f[*s], s + 1, ind); } } int query2(trie2 *r, char *s, int ind){ if(*s == 0){ int st, dr, mid; st = 0; dr = r->v.size() - 1; while(st <= dr){ mid = (st + dr) / 2; if(r->v[mid] <= ind){ dr = mid - 1; } else{ st = mid + 1; } } return r->v.size() - st; } if(r->f[*s] == NULL){ return 0; } return query2(r->f[*s], s + 1, ind); } void copiere(vector<char> v){ for(int i = 0; i < v.size(); i++){ p[i] = v[i]; } p[ v.size() ] = 0; } int main(){ r1 = new trie1; r2 = new trie2; cin>> n >> m; for(i = 1; i <= n; i++){ read(p); ind[i] = i; for(j = 0; j < k; j++){ v[i].push_back(p[j]); } } sort(ind + 1, ind + n + 1, cmp); for(i = 1; i <= n; i++){ copiere(v[ ind[i] ]); adauga1(r1, p, i); } for(i = 1; i <= m; i++){ read(p); w[i].ind = i; w[i].p = 1000000; query1(r1, p, w[i]); read(q); for(j = 0; j < k; j++){ c[i].push_back(q[j]); } } sort(w + 1, w + m + 1, cmp2); u = 1; for(ii = 1; ii <= n; ii++){ for(i = 0, j = v[ii].size() - 1; i < j; i++, j--){ swap(v[ii][i], v[ii][j]); } } for(ii = 1; ii <= m; ii++){ for(i = 0, j = c[ii].size() - 1; i < j; i++, j--){ swap(c[ii][i], c[ii][j]); } } while(w[u].p > n){ u++; } for(i = n; i >= 1; i--){ copiere(v[ ind[i] ]); adauga2(r2, p, i); while(w[u].p == i){ copiere(c[ w[u].ind ]); sol[ w[u].ind ] = query2(r2, p, w[u].u); u++; } } for(i = 1; i <= m; i++){ cout<< sol[i] <<"\n"; } }

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

selling_rna.cpp: In function 'int cmp(int, int)':
selling_rna.cpp:55:22: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   55 |     for(int i = 0; i < min(v[a].size(), v[b].size() ); i++){
      |                    ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'void adauga1(trie1*, char*, int)':
selling_rna.cpp:66:17: warning: array subscript has type 'char' [-Wchar-subscripts]
   66 |         if(r->f[*s] == NULL){
      |                 ^~
selling_rna.cpp:67:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   67 |             r->f[*s] = new trie1;
      |                  ^~
selling_rna.cpp:69:22: warning: array subscript has type 'char' [-Wchar-subscripts]
   69 |         adauga1(r->f[*s], s + 1, ind);
      |                      ^~
selling_rna.cpp: In function 'void query1(trie1*, char*, str&)':
selling_rna.cpp:78:17: warning: array subscript has type 'char' [-Wchar-subscripts]
   78 |         if(r->f[*s] != NULL){
      |                 ^~
selling_rna.cpp:79:25: warning: array subscript has type 'char' [-Wchar-subscripts]
   79 |             query1(r->f[*s], s + 1, w);
      |                         ^~
selling_rna.cpp: In function 'void adauga2(trie2*, char*, int)':
selling_rna.cpp:86:17: warning: array subscript has type 'char' [-Wchar-subscripts]
   86 |         if(r->f[*s] == NULL){
      |                 ^~
selling_rna.cpp:87:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   87 |             r->f[*s] = new trie2;
      |                  ^~
selling_rna.cpp:89:22: warning: array subscript has type 'char' [-Wchar-subscripts]
   89 |         adauga2(r->f[*s], s + 1, ind);
      |                      ^~
selling_rna.cpp: In function 'int query2(trie2*, char*, int)':
selling_rna.cpp:108:13: warning: array subscript has type 'char' [-Wchar-subscripts]
  108 |     if(r->f[*s] == NULL){
      |             ^~
selling_rna.cpp:111:24: warning: array subscript has type 'char' [-Wchar-subscripts]
  111 |     return query2(r->f[*s], s + 1, ind);
      |                        ^~
selling_rna.cpp: In function 'void copiere(std::vector<char>)':
selling_rna.cpp:114:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |     for(int i = 0; i < v.size(); i++){
      |                    ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...