oj.uz

답안 #98012

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
98012 2019-02-19T18:23:46 Z igzi Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 89 ms 29392 KB 
#include <bits/stdc++.h>
#define D 310
#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;

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,j,a,b,m;
for(i=0;i<s.size();i++){
    for(j=0;j<s.size();j++){
        a=0;
        b=v[i*D+j].size();
        if(b==0) continue;
        u.P=l[i];
        u.Q=d[j];
        while(b>a){
            m=(a+b)/2;
            if(poredi(v[i*D+j][m],u)) a=m+1;
            else b=m;
        }
        if(a!=v[i*D+j].size() && u.P==v[i*D+j][a].P && u.Q==v[i*D+j][a].Q){
        res[v[i*D+j][a].id]++;
        }
    }
}
}

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);
    }
    sort(y.begin(),y.end());
    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);
       int a,b;
       a=lower_bound(y.begin(),y.end(),s)-y.begin();
       b=upper_bound(y.begin(),y.end(),s)-y.begin();
       for(j=a;j<b;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++){
        sort(v[i].begin(),v[i].end(),poredi);
    }
    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:19:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<s.size();i++){
         ~^~~~~~~~~
selling_rna.cpp:20: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:32: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:51:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<s.size();i++){
         ~^~~~~~~~~
selling_rna.cpp:52:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(j=0;j<s.size();j++){
             ~^~~~~~~~~
selling_rna.cpp:63:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(a!=v[i*D+j].size() && u.P==v[i*D+j][a].P && u.Q==v[i*D+j][a].Q){
            ~^~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:86:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<y.size();i++){
             ~^~~~~~~~~
selling_rna.cpp:108:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<x.size();i++){
             ~^~~~~~~~~
selling_rna.cpp:112: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 11 ms 7424 KB Output is correct
2 Correct 9 ms 7296 KB Output is correct
3 Correct 8 ms 7296 KB Output is correct
4 Correct 10 ms 7296 KB Output is correct
5 Correct 10 ms 7296 KB Output is correct
6 Correct 8 ms 7372 KB Output is correct
7 Correct 9 ms 7296 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 89 ms 29392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 68 ms 10696 KB Output is correct
2 Correct 73 ms 9068 KB Output is correct
3 Correct 88 ms 9704 KB Output is correct
4 Correct 50 ms 9752 KB Output is correct
5 Correct 74 ms 9040 KB Output is correct
6 Correct 68 ms 9772 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 7424 KB Output is correct
2 Correct 9 ms 7296 KB Output is correct
3 Correct 8 ms 7296 KB Output is correct
4 Correct 10 ms 7296 KB Output is correct
5 Correct 10 ms 7296 KB Output is correct
6 Correct 8 ms 7372 KB Output is correct
7 Correct 9 ms 7296 KB Output is correct
8 Incorrect 89 ms 29392 KB Output isn't correct
9 Halted 0 ms 0 KB -