Submission #951872

# Submission time Handle Problem Language Result Execution time Memory
951872 2024-03-22T21:22:01 Z Saul0906 PIN (CEOI10_pin) C++14
45 / 100
1000 ms 18780 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, y;
	if(x){
		rep(j,0,10) if(j+'0'!=s[i]) 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-1,act->nxt[j+10]);
	}
	if(s[i]>'9' || s[i]<'0') y=s[i]-'a'+10;
	else y=s[i]-'0';
	ans+=solve(s,i+1,x,act->nxt[y]);
	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 4 ms 1368 KB Output is correct
2 Correct 35 ms 1312 KB Output is correct
3 Correct 259 ms 1140 KB Output is correct
4 Correct 52 ms 8020 KB Output is correct
5 Correct 69 ms 9728 KB Output is correct
6 Execution timed out 1035 ms 9664 KB Time limit exceeded
7 Correct 832 ms 8272 KB Output is correct
8 Correct 76 ms 10576 KB Output is correct
9 Correct 136 ms 16208 KB Output is correct
10 Execution timed out 1006 ms 10300 KB Time limit exceeded
11 Execution timed out 1076 ms 9968 KB Time limit exceeded
12 Execution timed out 1072 ms 4456 KB Time limit exceeded
13 Execution timed out 1060 ms 3608 KB Time limit exceeded
14 Execution timed out 1082 ms 2692 KB Time limit exceeded
15 Execution timed out 1066 ms 3580 KB Time limit exceeded
16 Correct 122 ms 18780 KB Output is correct
17 Execution timed out 1098 ms 11092 KB Time limit exceeded
18 Execution timed out 1060 ms 3108 KB Time limit exceeded
19 Execution timed out 1054 ms 3116 KB Time limit exceeded
20 Execution timed out 1047 ms 3412 KB Time limit exceeded