oj.uz

Submission #585957

# Submission time Handle Problem Language Result Execution time Memory
585957 2022-06-29T15:37:05 Z Ace Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1500 ms 143700 KB 
#include<bits/stdc++.h>
using namespace std;
 
typedef pair<int,int> pii;
typedef pair<pii,pii> piipii;
const int N = 1e5;
const int MULT = 23;
 
inline int getNum(char x){
	return x-'A'+1;
}
 
inline int getHash(string &s, int len){
	int ret = 0;
	for(int i=0;i<len;i++){
		ret *= MULT;
		ret += getNum(s[i]);
	}
	return ret;
}
 
map<int,int> memoDep[N+5];
map<int,int> memoBel[N+5];
string li[N+5];
 
int n,m;
 
string pre[N+5], suf[N+5];
set<int> isi[N+5];
set<int> dep, bel;
map<pii, int> cnt;
 
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		cin >> li[i];
	}
	for(int i=1;i<=m;i++){
		cin >> pre[i] >> suf[i];
		reverse(suf[i].begin(), suf[i].end());
		isi[pre[i].size()].insert(suf[i].size());
		dep.insert(pre[i].size());
		bel.insert(suf[i].size());
		cnt[make_pair(getHash(pre[i], pre[i].size()), getHash(suf[i], suf[i].size()))] = 0;
	}
	
	for(int i=1;i<=n;i++){
		int tmp = 0;
		int prev = 0;
		for(auto x: dep){
			if(x > li[i].size()) break;
			for(;prev<x;prev++){
				tmp *= MULT;
				tmp += getNum(li[i][prev]);
			}
			memoDep[i][x] = tmp;
		}
	}
	
	for(int i=1;i<=n;i++){
		int tmp = 0;
		int prev = 0;
		string tmps = li[i];
		reverse(tmps.begin(), tmps.end());
		for(auto x: bel){
			if(x > li[i].size()) break;
			for(;prev<x;prev++){
				tmp *= MULT;
				tmp += getNum(tmps[prev]);
			}
			memoBel[i][x] = tmp;
		}
	}
	
	for(int i=1;i<=n;i++){
		for(auto cand : dep){
			if(cand > li[i].size()) break;
			for(auto cand2: isi[cand]){
				if(cand2 > li[i].size()) break;
				pii tmp = make_pair(memoDep[i][cand], memoBel[i][cand2]);
				if(cnt.find(tmp) != cnt.end()) cnt[tmp]++;
			}
		}
	}
	
	for(int i=1;i<=m;i++){
		cout << cnt[make_pair(getHash(pre[i], pre[i].size()), getHash(suf[i], suf[i].size()))] << endl;
	}
	
	return 0;
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:52:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |    if(x > li[i].size()) break;
      |       ~~^~~~~~~~~~~~~~
selling_rna.cpp:67:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |    if(x > li[i].size()) break;
      |       ~~^~~~~~~~~~~~~~
selling_rna.cpp:78:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |    if(cand > li[i].size()) break;
      |       ~~~~~^~~~~~~~~~~~~~
selling_rna.cpp:80:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     if(cand2 > li[i].size()) break;
      |        ~~~~~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23764 KB Output is correct
2 Correct 13 ms 23784 KB Output is correct
3 Correct 14 ms 23808 KB Output is correct
4 Correct 13 ms 23820 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 13 ms 23724 KB Output is correct
7 Correct 13 ms 23780 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 562 ms 80100 KB Output is correct
2 Correct 1225 ms 116176 KB Output is correct
3 Correct 906 ms 103240 KB Output is correct
4 Correct 1042 ms 117100 KB Output is correct
5 Execution timed out 1589 ms 143700 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 29192 KB Output is correct
2 Correct 91 ms 31232 KB Output is correct
3 Correct 98 ms 31948 KB Output is correct
4 Correct 71 ms 27420 KB Output is correct
5 Correct 109 ms 31324 KB Output is correct
6 Correct 106 ms 31940 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23764 KB Output is correct
2 Correct 13 ms 23784 KB Output is correct
3 Correct 14 ms 23808 KB Output is correct
4 Correct 13 ms 23820 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 13 ms 23724 KB Output is correct
7 Correct 13 ms 23780 KB Output is correct
8 Correct 562 ms 80100 KB Output is correct
9 Correct 1225 ms 116176 KB Output is correct
10 Correct 906 ms 103240 KB Output is correct
11 Correct 1042 ms 117100 KB Output is correct
12 Execution timed out 1589 ms 143700 KB Time limit exceeded
13 Halted 0 ms 0 KB -