oj.uz

Submission #71093

# Submission time Handle Problem Language Result Execution time Memory
71093 2018-08-24T06:13:44 Z KLPP Selling RNA Strands (JOI16_selling_rna) C++14
0 / 100
 1500 ms 84468 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++){//inv hashing
		//cout<<arr[i]<<endl;
		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;
		}
		int lo=-1;
		int hi=n;
		while(hi-lo>1){
			int mid=(lo+hi)/2;
			bool b=true;
			bool b2=false;
			for(int i=0;i<p.size() && b && !b2;i++){
				int x=arr[mid].at(i);
				int y=p.at(i);
				if(arr[mid].size()<=i || arr[mid].at(i)<p.at(i))b=false;
				if(arr[mid].size()>i && x>y){//cout<<i<<" "<<x<<" "<<y<<endl;
					b2=true;
				}
			}//cout<<mid<<" "<<b<<" "<<b2<<endl;
			if(b && !b2)hi=mid;
			else lo=mid;
		}
		//cout<<lo<<" "<<hi<<" "<<p<<endl;
		//cout<<hi<<endl;
		int start=hi;
		lo=-1;
		hi=n;
		while(hi-lo>1){
			int mid=(lo+hi)/2;
			bool b=true;
			for(int i=0;i<p.size() && b;i++){
				if(arr[mid].size()<=i || arr[mid].at(i)<p.at(i))b=false;
			}//cout<<mid<<" "<<b<<endl;
			bool b2=true;
			for(int i=0;i<p.size();i++){
				if(arr[mid].size()<=i || arr[mid].at(i)!=p.at(i))b=false;
			}
			if(b && !b2)hi=mid;
			else lo=mid;
		}
		//cout<<lo<<" "<<hi<<endl;
		int end=lo;
		int cnt=0;
		//cout<<hashp<<endl;
		for(int i=start;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:49:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<arr[i].size();j++){
               ~^~~~~~~~~~~~~~
selling_rna.cpp:71:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<p.size();i++){
               ~^~~~~~~~~
selling_rna.cpp:83:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<p.size() && b && !b2;i++){
                ~^~~~~~~~~
selling_rna.cpp:86:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(arr[mid].size()<=i || arr[mid].at(i)<p.at(i))b=false;
        ~~~~~~~~~~~~~~~^~~
selling_rna.cpp:87:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(arr[mid].size()>i && x>y){//cout<<i<<" "<<x<<" "<<y<<endl;
        ~~~~~~~~~~~~~~~^~
selling_rna.cpp:102:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<p.size() && b;i++){
                ~^~~~~~~~~
selling_rna.cpp:103:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(arr[mid].size()<=i || arr[mid].at(i)<p.at(i))b=false;
        ~~~~~~~~~~~~~~~^~~
selling_rna.cpp:106:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<p.size();i++){
                ~^~~~~~~~~
selling_rna.cpp:107:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(arr[mid].size()<=i || arr[mid].at(i)!=p.at(i))b=false;
        ~~~~~~~~~~~~~~~^~~
selling_rna.cpp:113:7: warning: unused variable 'end' [-Wunused-variable]
   int end=lo;
       ^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 199 ms 84468 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -