답안 #98019 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
98019	2019-02-19T19:37:19 Z	igzi	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	980 ms	160760 KB

selling_rna

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #98019

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 25.0 / 25.0

Subtask #3 25.0 / 25.0

Subtask #4 40.0 / 40.0

Subtask #1
10.0 / 10.0

Subtask #2
25.0 / 25.0

Subtask #3
25.0 / 25.0

Subtask #4
40.0 / 40.0