oj.uz

Submission #933045

# Submission time Handle Problem Language Result Execution time Memory
933045 2024-02-24T23:06:46 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 480 ms 1048576 KB 
#include <bits/stdc++.h>
#define endl "\n"
#define rep(a,b,c) for(int a=b; a<c; a++)
#define repa(a,b) for(auto a:b)
#define pii pair<int, int>
#define fi first
#define se second
#define ll long long

using namespace std;

const int lim=1e5+5;

struct trie{
	trie *nxt[4]{};
	bitset<lim> bt;
} *pref, *suff;

int mp(char c){
	if(c=='A') return 0;
	if(c=='C') return 1;
	if(c=='G') return 2;
	return 3;
}

void add(string s, int p, int x){
	if(p&1){
		trie *act=pref;
		rep(i,0,s.size()){
			int nx=mp(s[i]);
			if(act->nxt[nx]==NULL) act->nxt[nx]=new trie;
			act=act->nxt[nx];
			act->bt.set(x);
		}
	}else{
		trie *act=suff;
		rep(i,0,s.size()){
			int nx=mp(s[i]);
			if(act->nxt[nx]==NULL) act->nxt[nx]=new trie;
			act=act->nxt[nx];
			act->bt.set(x);
		}
	}
}

int query(string a, string b){
	trie *bg=pref, *ed=suff;
	rep(i,0,a.size()){
		int nx=mp(a[i]);
		if(bg->nxt[nx]==NULL) return 0;
		bg=bg->nxt[nx];
	}
	rep(i,0,b.size()){
		int nx=mp(b[i]);
		if(ed->nxt[nx]==NULL) return 0;
		ed=ed->nxt[nx];
	}
	return ((bg->bt)&(ed->bt)).count();
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, q;
	string s, a, b;
	cin>>n>>q;
	pref=new trie;
	suff=new trie;
	rep(i,0,n){
		cin>>s;
		add(s,1,i);
		reverse(s.begin(),s.end());
		add(s,2,i);
	}
	while(q--){
		cin>>a>>b;
		reverse(b.begin(),b.end());
		cout<<query(a,b)<<endl;
	}
}

Compilation message

selling_rna.cpp: In function 'void add(std::string, int, int)':
selling_rna.cpp:3:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define rep(a,b,c) for(int a=b; a<c; a++)
......
   29 |   rep(i,0,s.size()){
      |       ~~~~~~~~~~~~                
selling_rna.cpp:29:3: note: in expansion of macro 'rep'
   29 |   rep(i,0,s.size()){
      |   ^~~
selling_rna.cpp:3:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define rep(a,b,c) for(int a=b; a<c; a++)
......
   37 |   rep(i,0,s.size()){
      |       ~~~~~~~~~~~~                
selling_rna.cpp:37:3: note: in expansion of macro 'rep'
   37 |   rep(i,0,s.size()){
      |   ^~~
selling_rna.cpp: In function 'int query(std::string, std::string)':
selling_rna.cpp:3:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define rep(a,b,c) for(int a=b; a<c; a++)
......
   48 |  rep(i,0,a.size()){
      |      ~~~~~~~~~~~~                 
selling_rna.cpp:48:2: note: in expansion of macro 'rep'
   48 |  rep(i,0,a.size()){
      |  ^~~
selling_rna.cpp:3:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define rep(a,b,c) for(int a=b; a<c; a++)
......
   53 |  rep(i,0,b.size()){
      |      ~~~~~~~~~~~~                 
selling_rna.cpp:53:2: note: in expansion of macro 'rep'
   53 |  rep(i,0,b.size()){
      |  ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3420 KB Output is correct
2 Correct 3 ms 3420 KB Output is correct
3 Correct 2 ms 3420 KB Output is correct
4 Correct 2 ms 3164 KB Output is correct
5 Correct 2 ms 3420 KB Output is correct
6 Correct 1 ms 2908 KB Output is correct
7 Correct 2 ms 3164 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 480 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 1112 KB Output is correct
2 Correct 167 ms 62804 KB Output is correct
3 Correct 200 ms 34392 KB Output is correct
4 Correct 152 ms 1116 KB Output is correct
5 Correct 170 ms 61256 KB Output is correct
6 Correct 198 ms 35416 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3420 KB Output is correct
2 Correct 3 ms 3420 KB Output is correct
3 Correct 2 ms 3420 KB Output is correct
4 Correct 2 ms 3164 KB Output is correct
5 Correct 2 ms 3420 KB Output is correct
6 Correct 1 ms 2908 KB Output is correct
7 Correct 2 ms 3164 KB Output is correct
8 Runtime error 480 ms 1048576 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -