oj.uz

Submission #98017

# Submission time Handle Problem Language Result Execution time Memory
98017 2019-02-19T19:36:05 Z igzi Selling RNA Strands (JOI16_selling_rna) C++17
60 / 100
 1500 ms 600836 KB 
#include <bits/stdc++.h>
#define D 5000
#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;
vector <pair<int,int>> p;
 
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,a,b,m,x,y;
for(i=0;i<p.size();i++){
        x=p[i].first;
        y=p[i].second;
        if(x>=s.size() || y>=s.size()) break;
        a=0;
        b=v[x*D+y].size();
        u.P=l[x];
        u.Q=d[y];
        while(b>a){
            m=(a+b)/2;
            if(poredi(v[x*D+y][m],u)) a=m+1;
            else b=m;
        }
        if(a!=v[x*D+y].size() && u.P==v[x*D+y][a].P && u.Q==v[x*D+y][a].Q){
        res[v[x*D+y][a].id]++;
        }
}
}
 
bool cmp(pair<int,int> a,pair<int,int> b){
return max(a.first,a.second)<max(b.first,b.second);
}
 
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++){
        if(v[i].size()==0) continue;
        sort(v[i].begin(),v[i].end(),poredi);
        p.push_back({i/D,i%D});
    }
    sort(p.begin(),p.end(),cmp);
    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:20:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<s.size();i++){
         ~^~~~~~~~~
selling_rna.cpp:21: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:33: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:52:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<p.size();i++){
         ~^~~~~~~~~
selling_rna.cpp:55:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(x>=s.size() || y>=s.size()) break;
            ~^~~~~~~~~~
selling_rna.cpp:55:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(x>=s.size() || y>=s.size()) break;
                           ~^~~~~~~~~~
selling_rna.cpp:65:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(a!=v[x*D+y].size() && u.P==v[x*D+y][a].P && u.Q==v[x*D+y][a].Q){
            ~^~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:90:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<y.size();i++){
             ~^~~~~~~~~
selling_rna.cpp:102:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
        for(j=0;j<y.size();j++){
                ~^~~~~~~~~
selling_rna.cpp:112:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<x.size();i++){
             ~^~~~~~~~~
selling_rna.cpp:116: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 760 ms 592112 KB Output is correct
2 Correct 688 ms 592160 KB Output is correct
3 Correct 692 ms 592212 KB Output is correct
4 Correct 707 ms 592120 KB Output is correct
5 Correct 675 ms 592248 KB Output is correct
6 Correct 665 ms 592120 KB Output is correct
7 Correct 672 ms 592112 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 780 ms 595092 KB Output is correct
2 Correct 886 ms 594932 KB Output is correct
3 Correct 826 ms 595004 KB Output is correct
4 Correct 834 ms 594956 KB Output is correct
5 Correct 1028 ms 594300 KB Output is correct
6 Correct 1045 ms 594292 KB Output is correct
7 Correct 924 ms 594552 KB Output is correct
8 Correct 751 ms 594876 KB Output is correct
9 Correct 766 ms 594932 KB Output is correct
10 Correct 1073 ms 595108 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 746 ms 596076 KB Output is correct
2 Correct 802 ms 594228 KB Output is correct
3 Correct 745 ms 595020 KB Output is correct
4 Correct 754 ms 595172 KB Output is correct
5 Correct 735 ms 594264 KB Output is correct
6 Correct 765 ms 595348 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 760 ms 592112 KB Output is correct
2 Correct 688 ms 592160 KB Output is correct
3 Correct 692 ms 592212 KB Output is correct
4 Correct 707 ms 592120 KB Output is correct
5 Correct 675 ms 592248 KB Output is correct
6 Correct 665 ms 592120 KB Output is correct
7 Correct 672 ms 592112 KB Output is correct
8 Correct 780 ms 595092 KB Output is correct
9 Correct 886 ms 594932 KB Output is correct
10 Correct 826 ms 595004 KB Output is correct
11 Correct 834 ms 594956 KB Output is correct
12 Correct 1028 ms 594300 KB Output is correct
13 Correct 1045 ms 594292 KB Output is correct
14 Correct 924 ms 594552 KB Output is correct
15 Correct 751 ms 594876 KB Output is correct
16 Correct 766 ms 594932 KB Output is correct
17 Correct 1073 ms 595108 KB Output is correct
18 Correct 746 ms 596076 KB Output is correct
19 Correct 802 ms 594228 KB Output is correct
20 Correct 745 ms 595020 KB Output is correct
21 Correct 754 ms 595172 KB Output is correct
22 Correct 735 ms 594264 KB Output is correct
23 Correct 765 ms 595348 KB Output is correct
24 Correct 1052 ms 596432 KB Output is correct
25 Correct 1044 ms 596652 KB Output is correct
26 Correct 977 ms 595360 KB Output is correct
27 Correct 999 ms 595540 KB Output is correct
28 Execution timed out 1532 ms 600836 KB Time limit exceeded
29 Halted 0 ms 0 KB -