답안 #98016 :: oj.uz

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

selling_rna

#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

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

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

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

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

답안 #98016

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