oj.uz

Submission #585349

# Submission time Handle Problem Language Result Execution time Memory
585349 2022-06-28T17:31:44 Z Ace Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1500 ms 140132 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';
}

inline pii getHash(string &s, int len){
	int ret = 0;
	for(int i=0;i<len;i++){
		ret *= MULT;
		ret += getNum(s[i]);
	}
	return make_pair(ret, len);
}

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<piipii, 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;
			piipii tmp = make_pair(make_pair(memoDep[i][cand.first], cand.first), make_pair(memoBel[i][cand.second], 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 13 ms 19028 KB Output is correct
2 Correct 13 ms 19024 KB Output is correct
3 Correct 10 ms 19028 KB Output is correct
4 Correct 13 ms 19028 KB Output is correct
5 Correct 11 ms 19028 KB Output is correct
6 Correct 12 ms 19028 KB Output is correct
7 Correct 10 ms 19028 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 544 ms 75020 KB Output is correct
2 Correct 1384 ms 110700 KB Output is correct
3 Correct 969 ms 101316 KB Output is correct
4 Correct 1179 ms 115136 KB Output is correct
5 Execution timed out 1581 ms 140132 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 24064 KB Output is correct
2 Correct 105 ms 26192 KB Output is correct
3 Correct 112 ms 26860 KB Output is correct
4 Correct 66 ms 22288 KB Output is correct
5 Correct 108 ms 26168 KB Output is correct
6 Correct 108 ms 26888 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19028 KB Output is correct
2 Correct 13 ms 19024 KB Output is correct
3 Correct 10 ms 19028 KB Output is correct
4 Correct 13 ms 19028 KB Output is correct
5 Correct 11 ms 19028 KB Output is correct
6 Correct 12 ms 19028 KB Output is correct
7 Correct 10 ms 19028 KB Output is correct
8 Correct 544 ms 75020 KB Output is correct
9 Correct 1384 ms 110700 KB Output is correct
10 Correct 969 ms 101316 KB Output is correct
11 Correct 1179 ms 115136 KB Output is correct
12 Execution timed out 1581 ms 140132 KB Time limit exceeded
13 Halted 0 ms 0 KB -