제출 #846642

#제출 시각아이디문제언어결과실행 시간메모리
846642dungzSelling RNA Strands (JOI16_selling_rna)C++17
10 / 100
265 ms261928 KiB
//dau tuyen //dau tuyen //dau tuyen #pragma GCC optimize ("O2") #include<bits/stdc++.h> using namespace std; #define ll long long #define fi first #define se second #define endl '\n' #define task "task" #define task "rna" #define prll pair<ll,ll> #define pb push_back #define ld long double const ll MIN=-1e18,MAX=1e18,MOD=1e9+7,nmax=1e5+5,nmax2=2e6+5,can=1400,base=31; string a[nmax]; pair<string,string> qu[nmax]; vector<ll> hash1[nmax]; ll hash2[nmax]; ll hash3[nmax]; ll P[nmax2]; int trie[can+5][5]; int trie2[can*5+5][can+5][5]; int sl[can*5+5][can*5+5]; int id=0,id2[can*5+5]; void build(string s1,string s2) { int p=0,p2=0; for(int i=1;i<s1.size();i++) { int ch=s1[i]-'A'; if(!trie[p][ch]) trie[p][ch]=++id; p=trie[p][ch]; } reverse(s2.begin(),s2.end()); for(int i=0;i<s2.size()-1;i++) { int ch=s2[i]-'A'; if(!trie2[p][p2][ch]) trie2[p][p2][ch]=++id2[p]; p2=trie2[p][p2][ch]; sl[p][p2]+=1; } } int get(string s1,string s2) { int p=0,p2=0; for(int i=1;i<s1.size();i++) { int ch=s1[i]-'A'; if(!trie[p][ch]) return 0; p=trie[p][ch]; } for(int i=0;i<s2.size()-1;i++) { int ch=s2[i]-'A'; if(!trie2[p][p2][ch]) return 0; p2=trie2[p][p2][ch]; } return sl[p][p2]; } ll gethash(int idx,int l,int r) { return ((hash1[idx][r]-hash1[idx][l-1]*P[r-l+1])+MOD*MOD)%MOD; } vector<int> grt,sml; int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int n,t; cin>>n>>t; for(int i=1;i<=n;i++) { cin>>a[i]; for(auto &i:a[i]) { if(i=='G') i='B'; if(i=='U') i='D'; } if(a[i].size()>can) grt.push_back(i); else sml.push_back(i); } for(int i=1;i<=t;i++) { cin>>qu[i].fi>>qu[i].se; for(auto &i:qu[i].fi) { if(i=='G') i='B'; if(i=='U') i='D'; } for(auto &i:qu[i].se) { if(i=='G') i='B'; if(i=='U') i='D'; } } P[0]=1; for(int i=1;i<=2000000;i++) P[i]=(P[i-1]*base)%MOD; for(int i=1;i<=n;i++) { a[i]=" "+a[i]; hash1[i].resize(a[i].size()); for(int j=1;j<a[i].size();j++) { hash1[i][j]=(hash1[i][j-1]*base+a[i][j]-'A'+1)%MOD; } } for(int i=1;i<=t;i++) { qu[i].fi=" "+qu[i].fi; qu[i].se=" "+qu[i].se; for(int j=1;j<qu[i].fi.size();j++) { hash2[i]=(hash2[i]*base+qu[i].fi[j]-'A'+1)%MOD; } for(int j=1;j<qu[i].se.size();j++) { hash3[i]=(hash3[i]*base+qu[i].se[j]-'A'+1)%MOD; } } for(auto i:sml) { string s=" "; for(int j=1;j<a[i].size();j++) { s+=a[i][j]; build(s,a[i]); } } for(int i=1;i<=t;i++) { int ans=0; for(auto j:grt) { if(gethash(j,1,qu[i].fi.size()-1)==hash2[i] and gethash(j,a[j].size()-qu[i].se.size()+1,a[j].size()-1)==hash3[i]) { ans++; } } if(qu[i].fi.size()<can and qu[i].se.size()<can) { reverse(qu[i].se.begin(),qu[i].se.end()); ans+=get(qu[i].fi,qu[i].se); } cout<<ans<<endl; } } /* */

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

selling_rna.cpp:12: warning: "task" redefined
   12 | #define task "rna"
      | 
selling_rna.cpp:11: note: this is the location of the previous definition
   11 | #define task "task"
      | 
selling_rna.cpp: In function 'void build(std::string, std::string)':
selling_rna.cpp:30:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(int i=1;i<s1.size();i++)
      |                 ~^~~~~~~~~~
selling_rna.cpp:37:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int i=0;i<s2.size()-1;i++)
      |                 ~^~~~~~~~~~~~
selling_rna.cpp: In function 'int get(std::string, std::string)':
selling_rna.cpp:48:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for(int i=1;i<s1.size();i++)
      |                 ~^~~~~~~~~~
selling_rna.cpp:54:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(int i=0;i<s2.size()-1;i++)
      |                 ~^~~~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:103:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |         for(int j=1;j<a[i].size();j++)
      |                     ~^~~~~~~~~~~~
selling_rna.cpp:112:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |         for(int j=1;j<qu[i].fi.size();j++)
      |                     ~^~~~~~~~~~~~~~~~
selling_rna.cpp:116:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |         for(int j=1;j<qu[i].se.size();j++)
      |                     ~^~~~~~~~~~~~~~~~
selling_rna.cpp:124:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |         for(int j=1;j<a[i].size();j++)
      |                     ~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...