oj.uz

Submission #97947

# Submission time Handle Problem Language Result Execution time Memory
97947 2019-02-19T15:31:35 Z igzi Selling RNA Strands (JOI16_selling_rna) C++17
60 / 100
 1500 ms 30084 KB 
#include <bits/stdc++.h>
#define D 310
#define maxN 100005

using namespace std;

vector <string> x,y;
string s,t;
int a[130],ans[maxN],res[maxN],i,j,n,m;
vector <int> l[maxN],d[maxN],tmp;

struct upit{
int P,Q,id;
};

vector <int> hesujP(string s){
int p=1,i,ans=0;
vector <int> res;
for(i=0;i<s.size();i++){
ans+=p*a[s[i]];
res.push_back(ans);
p*=5;
}
return res;
}

vector <int> hesujS(string s){
int i,ans=0;
vector <int> res;
for(i=s.size()-1;i>=0;i--){
ans*=5;
ans+=a[s[i]];
res.push_back(ans);
}
return res;
}

bool poredi(upit a,upit b){
if(a.P!=b.P) return a.P<b.P;
return a.Q<b.Q;
}

vector <upit> v[D*D+100];
upit u;

void resi(string s){
vector <int> l,d;
l=hesujP(s);
d=hesujS(s);
int i,j,a,b,m;
for(i=0;i<s.size();i++){
    for(j=0;j<s.size();j++){
        a=0;
        b=v[i*D+j].size();
        u.P=l[i];
        u.Q=d[j];
        while(b>a){
            m=(a+b)/2;
            if(poredi(v[i*D+j][m],u)) a=m+1;
            else b=m;
        }
        if(a!=v[i*D+j].size() && u.P==v[i*D+j][a].P && u.Q==v[i*D+j][a].Q){
        res[v[i*D+j][a].id]++;
        }
    }
}
}

int main()
{
    std::ios_base::sync_with_stdio(0);
    a['G']=1;
    a['U']=2;
    a['A']=3;
    a['C']=4;
    cin>>n>>m;
    for(i=0;i<n;i++){
    cin>>s;
    if(s.size()<=D) x.push_back(s);
    else y.push_back(s);
    }
    for(i=0;i<y.size();i++){
        l[i]=hesujP(y[i]);
        d[i]=hesujS(y[i]);
    }
    for(i=0;i<m;i++){
       cin>>s>>t;
       tmp=hesujP(s);
       u.P=tmp.back();
       tmp=hesujP(t);
       u.Q=tmp.back();
       u.id=i;
       if(s.size()<=D && t.size()<=D) v[(s.size()-1)*D+t.size()-1].push_back(u);
       for(j=0;j<y.size();j++){
        if(max(s.size(),t.size())<=y[j].size() && l[j][s.size()-1]==u.P && d[j][t.size()-1]==u.Q) ans[i]++;
       }
    }
    for(i=0;i<=D*D;i++){
        sort(v[i].begin(),v[i].end(),poredi);
    }
    for(i=0;i<x.size();i++){
        resi(x[i]);
    }
    for(i=0;i<=D*D;i++){
        for(j=1;j<v[i].size();j++){
            if(v[i][j].P==v[i][j-1].P && v[i][j].Q==v[i][j-1].Q) res[v[i][j].id]+=res[v[i][j-1].id];
        }
    }
    for(i=0;i<m;i++){
        cout<<ans[i]+res[i]<<"\n";
    }
    return 0;
}

Compilation message

selling_rna.cpp: In function 'std::vector<int> hesujP(std::__cxx11::string)':
selling_rna.cpp:19:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<s.size();i++){
         ~^~~~~~~~~
selling_rna.cpp:20:14: warning: array subscript has type 'char' [-Wchar-subscripts]
 ans+=p*a[s[i]];
              ^
selling_rna.cpp: In function 'std::vector<int> hesujS(std::__cxx11::string)':
selling_rna.cpp:32:12: warning: array subscript has type 'char' [-Wchar-subscripts]
 ans+=a[s[i]];
            ^
selling_rna.cpp: In function 'void resi(std::__cxx11::string)':
selling_rna.cpp:51:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<s.size();i++){
         ~^~~~~~~~~
selling_rna.cpp:52:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(j=0;j<s.size();j++){
             ~^~~~~~~~~
selling_rna.cpp:62:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(a!=v[i*D+j].size() && u.P==v[i*D+j][a].P && u.Q==v[i*D+j][a].Q){
            ~^~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:82:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<y.size();i++){
             ~^~~~~~~~~
selling_rna.cpp:94:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
        for(j=0;j<y.size();j++){
                ~^~~~~~~~~
selling_rna.cpp:101:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<x.size();i++){
             ~^~~~~~~~~
selling_rna.cpp:105:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=1;j<v[i].size();j++){
                 ~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7296 KB Output is correct
2 Correct 10 ms 7424 KB Output is correct
3 Correct 10 ms 7268 KB Output is correct
4 Correct 8 ms 7296 KB Output is correct
5 Correct 9 ms 7296 KB Output is correct
6 Correct 8 ms 7296 KB Output is correct
7 Correct 9 ms 7344 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 29944 KB Output is correct
2 Correct 437 ms 29308 KB Output is correct
3 Correct 256 ms 30072 KB Output is correct
4 Correct 362 ms 28924 KB Output is correct
5 Correct 538 ms 16376 KB Output is correct
6 Correct 594 ms 16760 KB Output is correct
7 Correct 210 ms 25208 KB Output is correct
8 Correct 370 ms 29812 KB Output is correct
9 Correct 331 ms 29812 KB Output is correct
10 Correct 451 ms 30084 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 10788 KB Output is correct
2 Correct 58 ms 9108 KB Output is correct
3 Correct 69 ms 9836 KB Output is correct
4 Correct 62 ms 9832 KB Output is correct
5 Correct 64 ms 9068 KB Output is correct
6 Correct 70 ms 9828 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7296 KB Output is correct
2 Correct 10 ms 7424 KB Output is correct
3 Correct 10 ms 7268 KB Output is correct
4 Correct 8 ms 7296 KB Output is correct
5 Correct 9 ms 7296 KB Output is correct
6 Correct 8 ms 7296 KB Output is correct
7 Correct 9 ms 7344 KB Output is correct
8 Correct 144 ms 29944 KB Output is correct
9 Correct 437 ms 29308 KB Output is correct
10 Correct 256 ms 30072 KB Output is correct
11 Correct 362 ms 28924 KB Output is correct
12 Correct 538 ms 16376 KB Output is correct
13 Correct 594 ms 16760 KB Output is correct
14 Correct 210 ms 25208 KB Output is correct
15 Correct 370 ms 29812 KB Output is correct
16 Correct 331 ms 29812 KB Output is correct
17 Correct 451 ms 30084 KB Output is correct
18 Correct 55 ms 10788 KB Output is correct
19 Correct 58 ms 9108 KB Output is correct
20 Correct 69 ms 9836 KB Output is correct
21 Correct 62 ms 9832 KB Output is correct
22 Correct 64 ms 9068 KB Output is correct
23 Correct 70 ms 9828 KB Output is correct
24 Execution timed out 1503 ms 25908 KB Time limit exceeded
25 Halted 0 ms 0 KB -