oj.uz

Submission #585953

# Submission time Handle Problem Language Result Execution time Memory
585953 2022-06-29T15:34:18 Z Ace Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1500 ms 140288 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<pii> isi;
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.insert(make_pair(pre[i].size(), 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: isi){
			if(cand.first > li[i].size() || cand.second > li[i].size()) continue;
			pii tmp = make_pair(memoDep[i][cand.first], memoBel[i][cand.second]);
			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:18: 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.first > li[i].size() || cand.second > li[i].size()) continue;
      |       ~~~~~~~~~~~^~~~~~~~~~~~~~
selling_rna.cpp:78:48: 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.first > li[i].size() || cand.second > li[i].size()) continue;
      |                                    ~~~~~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 10 ms 19168 KB Output is correct
3 Correct 9 ms 19028 KB Output is correct
4 Correct 11 ms 19036 KB Output is correct
5 Correct 11 ms 19096 KB Output is correct
6 Correct 13 ms 19028 KB Output is correct
7 Correct 10 ms 19108 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 499 ms 75024 KB Output is correct
2 Correct 1309 ms 114636 KB Output is correct
3 Correct 897 ms 101376 KB Output is correct
4 Correct 1173 ms 115192 KB Output is correct
5 Execution timed out 1561 ms 140288 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 24080 KB Output is correct
2 Correct 98 ms 26252 KB Output is correct
3 Correct 106 ms 27236 KB Output is correct
4 Correct 64 ms 22676 KB Output is correct
5 Correct 94 ms 26516 KB Output is correct
6 Correct 103 ms 27244 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 10 ms 19168 KB Output is correct
3 Correct 9 ms 19028 KB Output is correct
4 Correct 11 ms 19036 KB Output is correct
5 Correct 11 ms 19096 KB Output is correct
6 Correct 13 ms 19028 KB Output is correct
7 Correct 10 ms 19108 KB Output is correct
8 Correct 499 ms 75024 KB Output is correct
9 Correct 1309 ms 114636 KB Output is correct
10 Correct 897 ms 101376 KB Output is correct
11 Correct 1173 ms 115192 KB Output is correct
12 Execution timed out 1561 ms 140288 KB Time limit exceeded
13 Halted 0 ms 0 KB -