제출 #290392

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
290392		alexandra_udristoiu	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	537 ms	223896 KiB

selling_rna

#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++){
      |                    ~~^~~~~~~~~~

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