Submission #71061

#	Time	Username	Problem	Language	Result	Execution time	Memory
71061		KLPP	Selling RNA Strands (JOI16_selling_rna)	C++14	35 / 100	1588 ms	85332 KiB

selling_rna

#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 (stderr)

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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40