oj.uz

Submission #71061

# Submission time Handle Problem Language Result Execution time Memory
71061 2018-08-24T05:05:29 Z KLPP Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1500 ms 85332 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 4 ms 376 KB Output is correct
2 Correct 4 ms 600 KB Output is correct
3 Correct 3 ms 600 KB Output is correct
4 Correct 3 ms 600 KB Output is correct
5 Correct 4 ms 600 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 3 ms 600 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 46584 KB Output is correct
2 Correct 809 ms 55300 KB Output is correct
3 Correct 452 ms 57460 KB Output is correct
4 Correct 580 ms 63344 KB Output is correct
5 Correct 630 ms 63344 KB Output is correct
6 Correct 719 ms 63344 KB Output is correct
7 Correct 586 ms 63344 KB Output is correct
8 Correct 722 ms 76104 KB Output is correct
9 Correct 648 ms 81784 KB Output is correct
10 Correct 1163 ms 85332 KB Output is correct

Subtask #3
0 / 25.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 4 ms 600 KB Output is correct
3 Correct 3 ms 600 KB Output is correct
4 Correct 3 ms 600 KB Output is correct
5 Correct 4 ms 600 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 3 ms 600 KB Output is correct
8 Correct 335 ms 46584 KB Output is correct
9 Correct 809 ms 55300 KB Output is correct
10 Correct 452 ms 57460 KB Output is correct
11 Correct 580 ms 63344 KB Output is correct
12 Correct 630 ms 63344 KB Output is correct
13 Correct 719 ms 63344 KB Output is correct
14 Correct 586 ms 63344 KB Output is correct
15 Correct 722 ms 76104 KB Output is correct
16 Correct 648 ms 81784 KB Output is correct
17 Correct 1163 ms 85332 KB Output is correct
18 Execution timed out 1588 ms 85332 KB Time limit exceeded
19 Halted 0 ms 0 KB -