oj.uz

Submission #71087

# Submission time Handle Problem Language Result Execution time Memory
71087 2018-08-24T05:55:16 Z KLPP Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1500 ms 47480 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;
			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;
			if(b)hi=mid;
			else lo=mid;
		}
		//cout<<lo<<" "<<hi<<" "<<p<<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=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: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:82:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<p.size() && b;i++){
                ~^~~~~~~~~
selling_rna.cpp:83: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:95:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<p.size() && b;i++){
                ~^~~~~~~~~
selling_rna.cpp:96: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:99:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<p.size();i++){
                ~^~~~~~~~~
selling_rna.cpp:100: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:89:7: warning: unused variable 'start' [-Wunused-variable]
   int start=hi;
       ^~~~~
selling_rna.cpp:106:7: warning: unused variable 'end' [-Wunused-variable]
   int end=lo;
       ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Correct 3 ms 392 KB Output is correct
4 Correct 3 ms 392 KB Output is correct
5 Correct 3 ms 392 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 4 ms 524 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 42476 KB Output is correct
2 Correct 791 ms 47240 KB Output is correct
3 Correct 506 ms 47240 KB Output is correct
4 Correct 645 ms 47480 KB Output is correct
5 Correct 655 ms 47480 KB Output is correct
6 Correct 576 ms 47480 KB Output is correct
7 Correct 635 ms 47480 KB Output is correct
8 Correct 709 ms 47480 KB Output is correct
9 Correct 723 ms 47480 KB Output is correct
10 Correct 1160 ms 47480 KB Output is correct

Subtask #3
0 / 25.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Correct 3 ms 392 KB Output is correct
4 Correct 3 ms 392 KB Output is correct
5 Correct 3 ms 392 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 4 ms 524 KB Output is correct
8 Correct 355 ms 42476 KB Output is correct
9 Correct 791 ms 47240 KB Output is correct
10 Correct 506 ms 47240 KB Output is correct
11 Correct 645 ms 47480 KB Output is correct
12 Correct 655 ms 47480 KB Output is correct
13 Correct 576 ms 47480 KB Output is correct
14 Correct 635 ms 47480 KB Output is correct
15 Correct 709 ms 47480 KB Output is correct
16 Correct 723 ms 47480 KB Output is correct
17 Correct 1160 ms 47480 KB Output is correct
18 Execution timed out 1579 ms 47480 KB Time limit exceeded
19 Halted 0 ms 0 KB -