Submission #68407

#	Time	Username	Problem	Language	Result	Execution time	Memory
68407		KLPP	Selling RNA Strands (JOI16_selling_rna)	C++14	0 / 100	1560 ms	36404 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);
		}
	}
	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);
			v*=BASE;
			v%=MOD;
		}
		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;
	}
	
	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:58:7: warning: unused variable 'pos' [-Wunused-variable]
   int pos=0;
       ^~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40