Submission #951867

# Submission time Handle Problem Language Result Execution time Memory
951867 2024-03-22T21:17:50 Z Saul0906 PIN (CEOI10_pin) C++14
30 / 100
1000 ms 12968 KB
#include <bits/stdc++.h>
#define rep(a,b,c) for(int a=b; a<c; a++)
#define repa(a,b) for(auto a:b)
#define fi first
#define se second
#define pii pair<int, int>
#define ll long long
#define endl "\n"

using namespace std;

struct trie{
	trie *nxt[36];
	int cont=0;
} *TR =  new trie;

void add(string s){
	trie *act=TR;
	int x;
	rep(i,0,s.size()){
		if(s[i]>'9' || s[i]<'0') x=s[i]-'a'+10;
		else x=s[i]-'0';
		if(!(act->nxt[x])) act->nxt[x]=new trie;
		act=act->nxt[x];
		act->cont++;
	}
}

int solve(string s, int i, int x, trie *act){
	if(!act || x<0 || 4-i<x) return 0;
	if(i==4) return act->cont;
	int ans=0;
	rep(j,0,10){
		if(j+'0'==s[i]) ans+=solve(s,i+1,x,act->nxt[j]);
		else ans+=solve(s,i+1,x-1,act->nxt[j]);
	}
	rep(j,0,26){
		if(j+'a'==s[i]) ans+=solve(s,i+1,x,act->nxt[j+10]);
		else ans+=solve(s,i+1,x-1,act->nxt[j+10]);
	}
	return ans;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, d, ans=0;
	cin>>n>>d;
	string s[n];
	rep(i,0,n){
		cin>>s[i];
		ans+=solve(s[i],0,d,TR);
		add(s[i]);
	}
	cout<<ans<<endl;
}

Compilation message

pin.cpp: In function 'void add(std::string)':
pin.cpp:2:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define rep(a,b,c) for(int a=b; a<c; a++)
......
   20 |  rep(i,0,s.size()){
      |      ~~~~~~~~~~~~                 
pin.cpp:20:2: note: in expansion of macro 'rep'
   20 |  rep(i,0,s.size()){
      |  ^~~
# Verdict Execution time Memory Grader output
1 Correct 32 ms 1368 KB Output is correct
2 Correct 199 ms 1368 KB Output is correct
3 Correct 264 ms 1108 KB Output is correct
4 Correct 630 ms 8180 KB Output is correct
5 Correct 802 ms 9824 KB Output is correct
6 Execution timed out 1066 ms 3700 KB Time limit exceeded
7 Execution timed out 1058 ms 3540 KB Time limit exceeded
8 Correct 889 ms 10820 KB Output is correct
9 Execution timed out 1022 ms 12084 KB Time limit exceeded
10 Execution timed out 1054 ms 4680 KB Time limit exceeded
11 Execution timed out 1018 ms 3716 KB Time limit exceeded
12 Execution timed out 1099 ms 3408 KB Time limit exceeded
13 Execution timed out 1043 ms 2644 KB Time limit exceeded
14 Execution timed out 1064 ms 2572 KB Time limit exceeded
15 Execution timed out 1031 ms 3720 KB Time limit exceeded
16 Execution timed out 1012 ms 12968 KB Time limit exceeded
17 Execution timed out 1072 ms 4436 KB Time limit exceeded
18 Execution timed out 1037 ms 3256 KB Time limit exceeded
19 Execution timed out 1034 ms 3144 KB Time limit exceeded
20 Execution timed out 1044 ms 3888 KB Time limit exceeded