제출 #705620

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
705620		igzi	Selling RNA Strands (JOI16_selling_rna)	C++17	35 / 100	1556 ms	11604 KiB

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],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 <vector<upit>> v;
map<pair<int,int>,int> mp;
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;
		int tmp = mp[{x,y}];
        b=v[tmp].size();
        u.P=l[x-1];
        u.Q=d[y-1];
        while(b>a){
            m=(a+b)/2;
            if(poredi(v[tmp][m],u)) a=m+1;
            else b=m;
        }
 
		//cout<<a<<endl;
		//cout<<v[tmp][0].P<<" "<<v[tmp][0].Q<<endl;
		//cout<<v[tmp][1].P<<" "<<v[tmp][1].Q<<endl;
		//cout<<u.P<<" "<<u.Q<<" "<<u.id<<endl;
        if(a!=v[tmp].size() && u.P==v[tmp][a].P && u.Q==v[tmp][a].Q){
        ans[v[tmp][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;
    x.push_back(s);
    }
 
    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(mp.find({s.size(),t.size()})==mp.end()){
		mp[{s.size(),t.size()}]=v.size();
		p.push_back({s.size(),t.size()});
		vector<upit> tmp;
		tmp.push_back(u);
		v.push_back(tmp);
		}
		else {
			v[mp[{s.size(),t.size()}]].push_back(u);
		}
    }
    for(i=0;i<v.size();i++){
        sort(v[i].begin(),v[i].end(),poredi);
    }
    sort(p.begin(),p.end(),cmp);
    for(i=0;i<x.size();i++){
        resi(x[i]);
    }
    for(i=0;i<v.size();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) ans[v[i][j].id]+=ans[v[i][j-1].id];
        }
    }
    for(i=0;i<m;i++){
        cout<<ans[i]<<"\n";
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

selling_rna.cpp: In function 'std::vector<int> hesujP(std::string)':
selling_rna.cpp:20:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 | for(i=0;i<s.size();i++){
      |         ~^~~~~~~~~
selling_rna.cpp:21:14: warning: array subscript has type 'char' [-Wchar-subscripts]
   21 | ans+=p*a[s[i]];
      |              ^
selling_rna.cpp: In function 'std::vector<int> hesujS(std::string)':
selling_rna.cpp:33:12: warning: array subscript has type 'char' [-Wchar-subscripts]
   33 | ans+=a[s[i]];
      |            ^
selling_rna.cpp: In function 'void resi(std::string)':
selling_rna.cpp:53:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 | for(i=0;i<p.size();i++){
      |         ~^~~~~~~~~
selling_rna.cpp:56:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         if(x>s.size() || y>s.size()) break;
      |            ~^~~~~~~~~
selling_rna.cpp:56:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         if(x>s.size() || y>s.size()) break;
      |                          ~^~~~~~~~~
selling_rna.cpp:72:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<upit>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         if(a!=v[tmp].size() && u.P==v[tmp][a].P && u.Q==v[tmp][a].Q){
      |            ~^~~~~~~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:116:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<upit> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |     for(i=0;i<v.size();i++){
      |             ~^~~~~~~~~
selling_rna.cpp:120:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     for(i=0;i<x.size();i++){
      |             ~^~~~~~~~~
selling_rna.cpp:123:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<upit> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |     for(i=0;i<v.size();i++){
      |             ~^~~~~~~~~
selling_rna.cpp:124:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<upit>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |         for(j=1;j<v[i].size();j++){
      |                 ~^~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 25
• Subtask 3: 25 / 25
• Subtask 4: 0 / 40