oj.uz

Submission #101160

# Submission time Handle Problem Language Result Execution time Memory
101160 2019-03-17T07:00:54 Z autumn_eel Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1399 ms 50724 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 unsigned long long ull;
typedef pair<int,int>P;

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

ull get_hash(string&s){
	ull res=0;
	for(char c:s){
		res=res*B+c;
	}
	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;
	}
	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;
		ull 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:16: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:45: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:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",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);p[i]=S;
   ~~~~~^~~~~~~~
selling_rna.cpp:54: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 27 ms 25344 KB Output is correct
2 Correct 30 ms 25332 KB Output is correct
3 Correct 26 ms 25344 KB Output is correct
4 Correct 26 ms 25336 KB Output is correct
5 Correct 26 ms 25592 KB Output is correct
6 Correct 28 ms 25344 KB Output is correct
7 Correct 28 ms 25464 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 44996 KB Output is correct
2 Correct 566 ms 45272 KB Output is correct
3 Correct 263 ms 45304 KB Output is correct
4 Correct 350 ms 45304 KB Output is correct
5 Correct 572 ms 37916 KB Output is correct
6 Correct 582 ms 38168 KB Output is correct
7 Correct 365 ms 42748 KB Output is correct
8 Correct 359 ms 47232 KB Output is correct
9 Correct 370 ms 47276 KB Output is correct
10 Correct 1399 ms 45032 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 66 ms 50724 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 27 ms 25344 KB Output is correct
2 Correct 30 ms 25332 KB Output is correct
3 Correct 26 ms 25344 KB Output is correct
4 Correct 26 ms 25336 KB Output is correct
5 Correct 26 ms 25592 KB Output is correct
6 Correct 28 ms 25344 KB Output is correct
7 Correct 28 ms 25464 KB Output is correct
8 Correct 188 ms 44996 KB Output is correct
9 Correct 566 ms 45272 KB Output is correct
10 Correct 263 ms 45304 KB Output is correct
11 Correct 350 ms 45304 KB Output is correct
12 Correct 572 ms 37916 KB Output is correct
13 Correct 582 ms 38168 KB Output is correct
14 Correct 365 ms 42748 KB Output is correct
15 Correct 359 ms 47232 KB Output is correct
16 Correct 370 ms 47276 KB Output is correct
17 Correct 1399 ms 45032 KB Output is correct
18 Runtime error 66 ms 50724 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -