oj.uz

Submission #98018

# Submission time Handle Problem Language Result Execution time Memory
98018 2019-02-19T19:36:45 Z igzi Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 1311 ms 389140 KB 
#include <bits/stdc++.h>
#define D 4000
#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 464 ms 380832 KB Output is correct
2 Correct 491 ms 380876 KB Output is correct
3 Correct 461 ms 380792 KB Output is correct
4 Correct 448 ms 380916 KB Output is correct
5 Correct 446 ms 380892 KB Output is correct
6 Correct 493 ms 380920 KB Output is correct
7 Correct 474 ms 380932 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 508 ms 384112 KB Output is correct
2 Correct 617 ms 383224 KB Output is correct
3 Correct 572 ms 383248 KB Output is correct
4 Correct 632 ms 383220 KB Output is correct
5 Correct 810 ms 382712 KB Output is correct
6 Correct 843 ms 382824 KB Output is correct
7 Correct 702 ms 382624 KB Output is correct
8 Correct 517 ms 383372 KB Output is correct
9 Correct 542 ms 383272 KB Output is correct
10 Correct 1087 ms 383396 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 549 ms 384352 KB Output is correct
2 Correct 565 ms 382604 KB Output is correct
3 Correct 541 ms 383344 KB Output is correct
4 Correct 514 ms 383464 KB Output is correct
5 Correct 646 ms 382576 KB Output is correct
6 Correct 496 ms 383300 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 464 ms 380832 KB Output is correct
2 Correct 491 ms 380876 KB Output is correct
3 Correct 461 ms 380792 KB Output is correct
4 Correct 448 ms 380916 KB Output is correct
5 Correct 446 ms 380892 KB Output is correct
6 Correct 493 ms 380920 KB Output is correct
7 Correct 474 ms 380932 KB Output is correct
8 Correct 508 ms 384112 KB Output is correct
9 Correct 617 ms 383224 KB Output is correct
10 Correct 572 ms 383248 KB Output is correct
11 Correct 632 ms 383220 KB Output is correct
12 Correct 810 ms 382712 KB Output is correct
13 Correct 843 ms 382824 KB Output is correct
14 Correct 702 ms 382624 KB Output is correct
15 Correct 517 ms 383372 KB Output is correct
16 Correct 542 ms 383272 KB Output is correct
17 Correct 1087 ms 383396 KB Output is correct
18 Correct 549 ms 384352 KB Output is correct
19 Correct 565 ms 382604 KB Output is correct
20 Correct 541 ms 383344 KB Output is correct
21 Correct 514 ms 383464 KB Output is correct
22 Correct 646 ms 382576 KB Output is correct
23 Correct 496 ms 383300 KB Output is correct
24 Correct 823 ms 383900 KB Output is correct
25 Correct 799 ms 384640 KB Output is correct
26 Correct 803 ms 383604 KB Output is correct
27 Correct 799 ms 383864 KB Output is correct
28 Correct 1311 ms 389140 KB Output is correct
29 Correct 675 ms 388036 KB Output is correct