oj.uz

Submission #98016

# Submission time Handle Problem Language Result Execution time Memory
98016 2019-02-19T19:17:30 Z igzi Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 1047 ms 229224 KB 
#include <bits/stdc++.h>
#define D 3000
#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 270 ms 216440 KB Output is correct
2 Correct 264 ms 216440 KB Output is correct
3 Correct 257 ms 216440 KB Output is correct
4 Correct 261 ms 216316 KB Output is correct
5 Correct 254 ms 216492 KB Output is correct
6 Correct 272 ms 216568 KB Output is correct
7 Correct 270 ms 216312 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 222740 KB Output is correct
2 Correct 429 ms 218996 KB Output is correct
3 Correct 398 ms 219016 KB Output is correct
4 Correct 413 ms 218940 KB Output is correct
5 Correct 657 ms 218348 KB Output is correct
6 Correct 644 ms 218484 KB Output is correct
7 Correct 503 ms 218556 KB Output is correct
8 Correct 368 ms 219124 KB Output is correct
9 Correct 318 ms 219016 KB Output is correct
10 Correct 635 ms 219124 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 219980 KB Output is correct
2 Correct 300 ms 218492 KB Output is correct
3 Correct 304 ms 219112 KB Output is correct
4 Correct 292 ms 219036 KB Output is correct
5 Correct 325 ms 218300 KB Output is correct
6 Correct 310 ms 219116 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 216440 KB Output is correct
2 Correct 264 ms 216440 KB Output is correct
3 Correct 257 ms 216440 KB Output is correct
4 Correct 261 ms 216316 KB Output is correct
5 Correct 254 ms 216492 KB Output is correct
6 Correct 272 ms 216568 KB Output is correct
7 Correct 270 ms 216312 KB Output is correct
8 Correct 334 ms 222740 KB Output is correct
9 Correct 429 ms 218996 KB Output is correct
10 Correct 398 ms 219016 KB Output is correct
11 Correct 413 ms 218940 KB Output is correct
12 Correct 657 ms 218348 KB Output is correct
13 Correct 644 ms 218484 KB Output is correct
14 Correct 503 ms 218556 KB Output is correct
15 Correct 368 ms 219124 KB Output is correct
16 Correct 318 ms 219016 KB Output is correct
17 Correct 635 ms 219124 KB Output is correct
18 Correct 294 ms 219980 KB Output is correct
19 Correct 300 ms 218492 KB Output is correct
20 Correct 304 ms 219112 KB Output is correct
21 Correct 292 ms 219036 KB Output is correct
22 Correct 325 ms 218300 KB Output is correct
23 Correct 310 ms 219116 KB Output is correct
24 Correct 585 ms 219844 KB Output is correct
25 Correct 537 ms 220556 KB Output is correct
26 Correct 562 ms 223232 KB Output is correct
27 Correct 582 ms 223472 KB Output is correct
28 Correct 1047 ms 229224 KB Output is correct
29 Correct 400 ms 226336 KB Output is correct