# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
633180 | 2022-08-21T19:11:18 Z | Iwanttobreakfree | Selling RNA Strands (JOI16_selling_rna) | C++17 | 1500 ms | 42168 KB |
#include <iostream> #include <vector> using namespace std; #define int long long #define pii pair<int,int> const int mod=1e9+7,t=70,mod2=1e9+9,sz=101; vector<vector<int>> pre_hash; vector<int> pre; int get_hash(int a,int sz,int i){ int ans=(pre_hash[i][a+sz]-1ll*pre_hash[i][a]*pre[sz])%mod; if(ans<0)ans+=mod; return ans; } signed main(){ int n,m; cin>>n>>m; string s,st; pre_hash=vector<vector<int>> (n,vector<int>(sz)); pre=vector<int> (sz); pre[0]=1; vector<int> siz(n); for(int i=1;i<sz;i++)pre[i]=(pre[i-1]*t)%mod; for(int i=0;i<n;i++){ cin>>s; siz[i]=s.size(); for(int j=0;j<s.size();j++){ pre_hash[i][j+1]=(pre_hash[i][j]*t+s[j]-'A'+1)%mod; } } /*for(int i=0;i<n;i++){ for(int j=0;j<=siz[i];j++)cout<<pre_hash[i][j]<<' '; cout<<'\n'; }*/ while(m--){ cin>>s>>st; int hash1=0,hash2=0; for(int i=0;i<s.size();i++){ hash1=(hash1*t+s[i]-'A'+1)%mod; } for(int i=0;i<st.size();i++){ hash2=(hash2*t+st[i]-'A'+1)%mod; } //cout<<hash1<<' '<<hash2<<'\n'; int ans=0; for(int i=0;i<n;i++){ if(siz[i]>=max(s.size(),st.size())&&hash1==get_hash(0,s.size(),i)&&hash2==get_hash(siz[i]-st.size(),st.size(),i))ans++; } cout<<ans<<'\n'; } }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 340 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
7 | Correct | 1 ms | 340 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 121 ms | 7704 KB | Execution killed with signal 6 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1587 ms | 42168 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 340 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
7 | Correct | 1 ms | 340 KB | Output is correct |
8 | Runtime error | 121 ms | 7704 KB | Execution killed with signal 6 |
9 | Halted | 0 ms | 0 KB | - |