oj.uz

답안 #101157

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
101157 2019-03-17T06:55:51 Z autumn_eel Selling RNA Strands (JOI16_selling_rna) C++14
10 / 100
 1500 ms 53368 KB 
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

ll B=10007;
ll mul[200000];
struct rolling_hash{
	vector<ll>hsh;
	rolling_hash(){}
	rolling_hash(string&s){
		hsh=vector<ll>(s.size()+1);
		for(int i=1;i<=s.size();i++){
			hsh[i]=(hsh[i-1]*B+s[i-1])%MOD;
		}
	}
	ll get(){
		return hsh.back();
	}
	ll get(int l,int r){//[l,r)
		return (hsh[r]+MOD-hsh[l]*mul[r-l]%MOD)%MOD;
	}
};

char S[200000];
string s[200000],p[200000],q[200000];
rolling_hash rh[200000];

int main(){
	mul[0]=1;
	for(int i=1;i<200000;i++){
		mul[i]=(mul[i-1]*B)%MOD;
	}
	int n,m;scanf("%d%d",&n,&m);
	if(n>5000||m>5000)abort();
	rep(i,n){
		scanf("%s",S);
		s[i]=S;
		rh[i]=rolling_hash(s[i]);
	}
	rep(i,m){
		scanf("%s",S);p[i]=S;
		scanf("%s",S);q[i]=S;
		rolling_hash a(p[i]),b(q[i]);
		int cnt=0;
		rep(j,n){
			if(p[i].size()>s[j].size()||q[i].size()>s[j].size())continue;
			if(rh[j].get(0,p[i].size())==a.get()&&
				rh[j].get(s[j].size()-q[i].size(),s[j].size())==b.get())cnt++;
		}
		printf("%d\n",cnt);
	}
}

Compilation message

selling_rna.cpp: In constructor 'rolling_hash::rolling_hash(std::__cxx11::string&)':
selling_rna.cpp:15:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1;i<=s.size();i++){
               ~^~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:36:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n,m;scanf("%d%d",&n,&m);
          ~~~~~^~~~~~~~~~~~~~
selling_rna.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",S);
   ~~~~~^~~~~~~~
selling_rna.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",S);p[i]=S;
   ~~~~~^~~~~~~~
selling_rna.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",S);q[i]=S;
   ~~~~~^~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 25344 KB Output is correct
2 Correct 27 ms 25344 KB Output is correct
3 Correct 26 ms 25344 KB Output is correct
4 Correct 27 ms 25316 KB Output is correct
5 Correct 29 ms 25408 KB Output is correct
6 Correct 27 ms 25344 KB Output is correct
7 Correct 28 ms 25344 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 278 ms 45056 KB Output is correct
2 Correct 1124 ms 45304 KB Output is correct
3 Correct 411 ms 49204 KB Output is correct
4 Correct 516 ms 49180 KB Output is correct
5 Correct 947 ms 40568 KB Output is correct
6 Correct 885 ms 40800 KB Output is correct
7 Correct 672 ms 48200 KB Output is correct
8 Correct 636 ms 53368 KB Output is correct
9 Correct 530 ms 53124 KB Output is correct
10 Execution timed out 1547 ms 47784 KB Time limit exceeded

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 60 ms 50560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 25344 KB Output is correct
2 Correct 27 ms 25344 KB Output is correct
3 Correct 26 ms 25344 KB Output is correct
4 Correct 27 ms 25316 KB Output is correct
5 Correct 29 ms 25408 KB Output is correct
6 Correct 27 ms 25344 KB Output is correct
7 Correct 28 ms 25344 KB Output is correct
8 Correct 278 ms 45056 KB Output is correct
9 Correct 1124 ms 45304 KB Output is correct
10 Correct 411 ms 49204 KB Output is correct
11 Correct 516 ms 49180 KB Output is correct
12 Correct 947 ms 40568 KB Output is correct
13 Correct 885 ms 40800 KB Output is correct
14 Correct 672 ms 48200 KB Output is correct
15 Correct 636 ms 53368 KB Output is correct
16 Correct 530 ms 53124 KB Output is correct
17 Execution timed out 1547 ms 47784 KB Time limit exceeded