oj.uz

Submission #101158

# Submission time Handle Problem Language Result Execution time Memory
101158 2019-03-17T06:58:17 Z autumn_eel Selling RNA Strands (JOI16_selling_rna) C++14
10 / 100
 1500 ms 50552 KB 
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

ll B=10007;
ll mul[200000];
struct rolling_hash{
	vector<ll>hsh;
	rolling_hash(){}
	rolling_hash(string&s){
		hsh=vector<ll>(s.size()+1);
		for(int i=1;i<=s.size();i++){
			hsh[i]=(hsh[i-1]*B+s[i-1])%MOD;
		}
	}
	ll get(){
		return hsh.back();
	}
	ll get(int l,int r){//[l,r)
		return (hsh[r]+MOD-hsh[l]*mul[r-l]%MOD)%MOD;
	}
};

ll get_hash(string&s){
	ll res=0;
	for(char c:s){
		res=(res*B+c)%MOD;
	}
	return res;
}

char S[200000];
string s[200000],p[200000],q[200000];
rolling_hash rh[200000];

int main(){
	mul[0]=1;
	for(int i=1;i<200000;i++){
		mul[i]=(mul[i-1]*B)%MOD;
	}
	int n,m;scanf("%d%d",&n,&m);
	if(n>5000||m>5000)abort();
	rep(i,n){
		scanf("%s",S);
		s[i]=S;
		rh[i]=rolling_hash(s[i]);
	}
	rep(i,m){
		scanf("%s",S);p[i]=S;
		scanf("%s",S);q[i]=S;
		ll a=get_hash(p[i]),b=get_hash(q[i]);
		int cnt=0;
		rep(j,n){
			if(p[i].size()>s[j].size()||q[i].size()>s[j].size())continue;
			if(rh[j].get(0,p[i].size())==a&&
				rh[j].get(s[j].size()-q[i].size(),s[j].size())==b)cnt++;
		}
		printf("%d\n",cnt);
	}
}

Compilation message

selling_rna.cpp: In constructor 'rolling_hash::rolling_hash(std::__cxx11::string&)':
selling_rna.cpp:15:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1;i<=s.size();i++){
               ~^~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:44:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n,m;scanf("%d%d",&n,&m);
          ~~~~~^~~~~~~~~~~~~~
selling_rna.cpp:47:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",S);
   ~~~~~^~~~~~~~
selling_rna.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",S);p[i]=S;
   ~~~~~^~~~~~~~
selling_rna.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",S);q[i]=S;
   ~~~~~^~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 25464 KB Output is correct
2 Correct 27 ms 25336 KB Output is correct
3 Correct 31 ms 25336 KB Output is correct
4 Correct 27 ms 25336 KB Output is correct
5 Correct 32 ms 25336 KB Output is correct
6 Correct 26 ms 25344 KB Output is correct
7 Correct 26 ms 25464 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 45020 KB Output is correct
2 Correct 1043 ms 45464 KB Output is correct
3 Correct 356 ms 45172 KB Output is correct
4 Correct 428 ms 45168 KB Output is correct
5 Correct 907 ms 38068 KB Output is correct
6 Correct 894 ms 38036 KB Output is correct
7 Correct 638 ms 42936 KB Output is correct
8 Correct 575 ms 47340 KB Output is correct
9 Correct 483 ms 47224 KB Output is correct
10 Execution timed out 1552 ms 44508 KB Time limit exceeded

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 57 ms 50552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 25464 KB Output is correct
2 Correct 27 ms 25336 KB Output is correct
3 Correct 31 ms 25336 KB Output is correct
4 Correct 27 ms 25336 KB Output is correct
5 Correct 32 ms 25336 KB Output is correct
6 Correct 26 ms 25344 KB Output is correct
7 Correct 26 ms 25464 KB Output is correct
8 Correct 273 ms 45020 KB Output is correct
9 Correct 1043 ms 45464 KB Output is correct
10 Correct 356 ms 45172 KB Output is correct
11 Correct 428 ms 45168 KB Output is correct
12 Correct 907 ms 38068 KB Output is correct
13 Correct 894 ms 38036 KB Output is correct
14 Correct 638 ms 42936 KB Output is correct
15 Correct 575 ms 47340 KB Output is correct
16 Correct 483 ms 47224 KB Output is correct
17 Execution timed out 1552 ms 44508 KB Time limit exceeded