Submission #933045

#	Time	Username	Problem	Language	Result	Execution time	Memory
933045		vjudge1	Selling RNA Strands (JOI16_selling_rna)	C++17	35 / 100	480 ms	1048576 KiB

selling_rna

#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 (stderr)

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 / 10
• Subtask 2: 0 / 25
• Subtask 3: 25 / 25
• Subtask 4: 0 / 40