oj.uz

Submission #68419

# Submission time Handle Problem Language Result Execution time Memory
68419 2018-08-17T06:14:53 Z KLPP Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1500 ms 75428 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#include<stdio.h>
using namespace std;
#define MOD 1000000007
#define BASE 257
typedef long long int lld;
bool cmp(string a, string b){
	for(int i=0;i<a.size() && i<b.size();i++){
		if(a.at(i)<b.at(i))return true;
		if(a.at(i)>b.at(i))return false;
	}
	if(a.length()<=b.length())return true;
	return false;
}
bool cmp2(string a, string b){
	for(int i=0;i<a.size() && i<b.size();i++){
		if(a.at(i)<b.at(i))return true;
		if(a.at(i)>b.at(i))return false;
	}
	if(a.length()>b.length())return true;
	return false;
}
int main(){
	int n,m;
	cin>>n>>m;
	string arr[n];
	for(int i=0;i<n;i++){
		cin>>arr[i];
	}
	//sort(arr,arr+n);
	vector<lld> hashes[n];
	for(int i=0;i<n;i++){
		lld v=1;
		lld h=0;
		for(int j=arr[i].size()-1;j>-1;j--){
			h+=v*arr[i].at(j);
			h%=MOD;
			v*=BASE;
			v%=MOD;
			hashes[i].push_back(h);
		}
	}vector<lld> hashes2[n];
	for(int i=0;i<n;i++){
		lld v=1;
		lld h=0;
		for(int j=0;j<arr[i].size();j++){
			h+=v*arr[i].at(j);
			h%=MOD;
			v*=BASE;
			v%=MOD;
			hashes2[i].push_back(h);
			//cout<<h<<" "<<v<<"  ";
		}//cout<<endl;
	}
	while(m--){
		string p,q;
		cin>>p>>q;
		lld hashq=0;
		lld v=1;
		for(int i=q.size()-1;i>-1;i--){
			hashq+=v*q.at(i);
			hashq%=MOD;
			v*=BASE;
			v%=MOD;
		}
		lld hashp=0;
		v=1;
		for(int i=0;i<p.size();i++){
			hashp+=v*p.at(i);
			hashp%=MOD;
			v*=BASE;
			v%=MOD;
		}//cout<<hashp<<" "<<v<<"  "<<endl;
		/*int lo,hi;
		lo=-1;
		hi=n;
		int pos=0;
		while(hi-lo>1){
			int mid=(hi+lo)/2;
			if(cmp(p,arr[mid]))hi=mid;
			else lo=mid;
		}
		int comeco=hi;
		lo=comeco-1;
		hi=n;
		while(hi-lo>1){
			int mid=(hi+lo)/2;
			if(cmp2(p,arr[mid]))hi=mid;
			else lo=mid;
		}
		int fim=lo;
		int cnt=0;
		//cout<<comeco<<" "<<fim<<endl;
		//cout<<hashq<<endl;*/
		/*for(int i=comeco;i<=fim;i++){
			if(hashes[i].size()>=q.length() && hashes[i][q.length()-1]==hashq){
				cnt++;
			}
		}cout<<cnt<<endl;*/
		int cnt=0;
		//cout<<hashp<<endl;
		for(int i=0;i<n;i++){
			if(hashes2[i].size()>=p.length() && hashes[i].size()>=q.length()){
				if(hashes2[i][p.length()-1]==hashp && hashes[i][q.length()-1]==hashq){
					cnt++;//cout<<i<<" ";
				}
			}
		}cout<<cnt<<endl;
		//cout<<endl;
	}
	
	return 0;
}

Compilation message

selling_rna.cpp: In function 'bool cmp(std::__cxx11::string, std::__cxx11::string)':
selling_rna.cpp:10:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a.size() && i<b.size();i++){
              ~^~~~~~~~~
selling_rna.cpp:10:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a.size() && i<b.size();i++){
                            ~^~~~~~~~~
selling_rna.cpp: In function 'bool cmp2(std::__cxx11::string, std::__cxx11::string)':
selling_rna.cpp:18:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a.size() && i<b.size();i++){
              ~^~~~~~~~~
selling_rna.cpp:18:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a.size() && i<b.size();i++){
                            ~^~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:48:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<arr[i].size();j++){
               ~^~~~~~~~~~~~~~
selling_rna.cpp:70:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<p.size();i++){
               ~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 360 KB Output is correct
3 Correct 2 ms 400 KB Output is correct
4 Correct 2 ms 420 KB Output is correct
5 Correct 2 ms 420 KB Output is correct
6 Correct 2 ms 472 KB Output is correct
7 Correct 2 ms 532 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 44928 KB Output is correct
2 Correct 634 ms 49296 KB Output is correct
3 Correct 449 ms 49296 KB Output is correct
4 Correct 554 ms 53020 KB Output is correct
5 Correct 542 ms 53020 KB Output is correct
6 Correct 599 ms 53020 KB Output is correct
7 Correct 489 ms 53020 KB Output is correct
8 Correct 603 ms 66160 KB Output is correct
9 Correct 565 ms 71788 KB Output is correct
10 Correct 934 ms 75428 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1563 ms 75428 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 360 KB Output is correct
3 Correct 2 ms 400 KB Output is correct
4 Correct 2 ms 420 KB Output is correct
5 Correct 2 ms 420 KB Output is correct
6 Correct 2 ms 472 KB Output is correct
7 Correct 2 ms 532 KB Output is correct
8 Correct 309 ms 44928 KB Output is correct
9 Correct 634 ms 49296 KB Output is correct
10 Correct 449 ms 49296 KB Output is correct
11 Correct 554 ms 53020 KB Output is correct
12 Correct 542 ms 53020 KB Output is correct
13 Correct 599 ms 53020 KB Output is correct
14 Correct 489 ms 53020 KB Output is correct
15 Correct 603 ms 66160 KB Output is correct
16 Correct 565 ms 71788 KB Output is correct
17 Correct 934 ms 75428 KB Output is correct
18 Execution timed out 1563 ms 75428 KB Time limit exceeded
19 Halted 0 ms 0 KB -