oj.uz

Submission #97945

# Submission time Handle Problem Language Result Execution time Memory
97945 2019-02-19T15:10:12 Z igzi Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 30108 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],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;
        }
        while(a!=v[i*D+j].size() && u.P==v[i*D+j][a].P && u.Q==v[i*D+j][a].Q){
        ans[v[i*D+j][a].id]++;
        a++;
        }
    }
}
}

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<m;i++){
        cout<<ans[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:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(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:83:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<y.size();i++){
             ~^~~~~~~~~
selling_rna.cpp:95:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
        for(j=0;j<y.size();j++){
                ~^~~~~~~~~
selling_rna.cpp:102:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<x.size();i++){
             ~^~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 29896 KB Output is correct
2 Correct 467 ms 29176 KB Output is correct
3 Correct 259 ms 29948 KB Output is correct
4 Correct 390 ms 28792 KB Output is correct
5 Correct 662 ms 16504 KB Output is correct
6 Correct 568 ms 16852 KB Output is correct
7 Correct 301 ms 25360 KB Output is correct
8 Correct 354 ms 29812 KB Output is correct
9 Correct 355 ms 29864 KB Output is correct
10 Correct 548 ms 30108 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1561 ms 10472 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7296 KB Output is correct
2 Correct 9 ms 7296 KB Output is correct
3 Correct 11 ms 7296 KB Output is correct
4 Correct 9 ms 7296 KB Output is correct
5 Correct 11 ms 7296 KB Output is correct
6 Correct 11 ms 7296 KB Output is correct
7 Correct 8 ms 7296 KB Output is correct
8 Correct 180 ms 29896 KB Output is correct
9 Correct 467 ms 29176 KB Output is correct
10 Correct 259 ms 29948 KB Output is correct
11 Correct 390 ms 28792 KB Output is correct
12 Correct 662 ms 16504 KB Output is correct
13 Correct 568 ms 16852 KB Output is correct
14 Correct 301 ms 25360 KB Output is correct
15 Correct 354 ms 29812 KB Output is correct
16 Correct 355 ms 29864 KB Output is correct
17 Correct 548 ms 30108 KB Output is correct
18 Execution timed out 1561 ms 10472 KB Time limit exceeded
19 Halted 0 ms 0 KB -