oj.uz

Submission #98010

# Submission time Handle Problem Language Result Execution time Memory
98010 2019-02-19T18:10:04 Z igzi Selling RNA Strands (JOI16_selling_rna) C++17
60 / 100
 1500 ms 30200 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();
        if(b==0) continue;
        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);
    //ifstream cin ("input.txt");
    cin.tie(NULL);
    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:63: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:85:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<y.size();i++){
             ~^~~~~~~~~
selling_rna.cpp:97:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
        for(j=0;j<y.size();j++){
                ~^~~~~~~~~
selling_rna.cpp:104:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<x.size();i++){
             ~^~~~~~~~~
selling_rna.cpp:108: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 11 ms 7296 KB Output is correct
2 Correct 10 ms 7296 KB Output is correct
3 Correct 10 ms 7296 KB Output is correct
4 Correct 10 ms 7296 KB Output is correct
5 Correct 9 ms 7296 KB Output is correct
6 Correct 10 ms 7296 KB Output is correct
7 Correct 9 ms 7296 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 30200 KB Output is correct
2 Correct 407 ms 29264 KB Output is correct
3 Correct 195 ms 29944 KB Output is correct
4 Correct 301 ms 28920 KB Output is correct
5 Correct 475 ms 16504 KB Output is correct
6 Correct 501 ms 17020 KB Output is correct
7 Correct 218 ms 25340 KB Output is correct
8 Correct 337 ms 30068 KB Output is correct
9 Correct 302 ms 29912 KB Output is correct
10 Correct 469 ms 30068 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 10816 KB Output is correct
2 Correct 60 ms 9196 KB Output is correct
3 Correct 64 ms 9832 KB Output is correct
4 Correct 44 ms 9936 KB Output is correct
5 Correct 56 ms 9200 KB Output is correct
6 Correct 68 ms 9832 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7296 KB Output is correct
2 Correct 10 ms 7296 KB Output is correct
3 Correct 10 ms 7296 KB Output is correct
4 Correct 10 ms 7296 KB Output is correct
5 Correct 9 ms 7296 KB Output is correct
6 Correct 10 ms 7296 KB Output is correct
7 Correct 9 ms 7296 KB Output is correct
8 Correct 131 ms 30200 KB Output is correct
9 Correct 407 ms 29264 KB Output is correct
10 Correct 195 ms 29944 KB Output is correct
11 Correct 301 ms 28920 KB Output is correct
12 Correct 475 ms 16504 KB Output is correct
13 Correct 501 ms 17020 KB Output is correct
14 Correct 218 ms 25340 KB Output is correct
15 Correct 337 ms 30068 KB Output is correct
16 Correct 302 ms 29912 KB Output is correct
17 Correct 469 ms 30068 KB Output is correct
18 Correct 55 ms 10816 KB Output is correct
19 Correct 60 ms 9196 KB Output is correct
20 Correct 64 ms 9832 KB Output is correct
21 Correct 44 ms 9936 KB Output is correct
22 Correct 56 ms 9200 KB Output is correct
23 Correct 68 ms 9832 KB Output is correct
24 Correct 1206 ms 25116 KB Output is correct
25 Execution timed out 1560 ms 29308 KB Time limit exceeded
26 Halted 0 ms 0 KB -