oj.uz

Submission #98019

# Submission time Handle Problem Language Result Execution time Memory
98019 2019-02-19T19:37:19 Z igzi Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 980 ms 160760 KB 
#include <bits/stdc++.h>
#define D 2500
#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 185 ms 151960 KB Output is correct
2 Correct 174 ms 151800 KB Output is correct
3 Correct 177 ms 151800 KB Output is correct
4 Correct 176 ms 151928 KB Output is correct
5 Correct 175 ms 151900 KB Output is correct
6 Correct 177 ms 152056 KB Output is correct
7 Correct 175 ms 151800 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 160760 KB Output is correct
2 Correct 380 ms 154228 KB Output is correct
3 Correct 331 ms 155888 KB Output is correct
4 Correct 323 ms 154228 KB Output is correct
5 Correct 535 ms 153844 KB Output is correct
6 Correct 540 ms 153716 KB Output is correct
7 Correct 411 ms 153700 KB Output is correct
8 Correct 233 ms 154480 KB Output is correct
9 Correct 233 ms 154260 KB Output is correct
10 Correct 564 ms 154356 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 155240 KB Output is correct
2 Correct 224 ms 153668 KB Output is correct
3 Correct 224 ms 154472 KB Output is correct
4 Correct 215 ms 154372 KB Output is correct
5 Correct 273 ms 153716 KB Output is correct
6 Correct 236 ms 154492 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 151960 KB Output is correct
2 Correct 174 ms 151800 KB Output is correct
3 Correct 177 ms 151800 KB Output is correct
4 Correct 176 ms 151928 KB Output is correct
5 Correct 175 ms 151900 KB Output is correct
6 Correct 177 ms 152056 KB Output is correct
7 Correct 175 ms 151800 KB Output is correct
8 Correct 245 ms 160760 KB Output is correct
9 Correct 380 ms 154228 KB Output is correct
10 Correct 331 ms 155888 KB Output is correct
11 Correct 323 ms 154228 KB Output is correct
12 Correct 535 ms 153844 KB Output is correct
13 Correct 540 ms 153716 KB Output is correct
14 Correct 411 ms 153700 KB Output is correct
15 Correct 233 ms 154480 KB Output is correct
16 Correct 233 ms 154260 KB Output is correct
17 Correct 564 ms 154356 KB Output is correct
18 Correct 231 ms 155240 KB Output is correct
19 Correct 224 ms 153668 KB Output is correct
20 Correct 224 ms 154472 KB Output is correct
21 Correct 215 ms 154372 KB Output is correct
22 Correct 273 ms 153716 KB Output is correct
23 Correct 236 ms 154492 KB Output is correct
24 Correct 494 ms 154836 KB Output is correct
25 Correct 475 ms 155660 KB Output is correct
26 Correct 458 ms 154608 KB Output is correct
27 Correct 514 ms 154992 KB Output is correct
28 Correct 980 ms 160324 KB Output is correct
29 Correct 383 ms 158688 KB Output is correct