/*
ID: noszaly1
TASK: {TASK}
LANG: C++11
*/
//Noszály Áron 11o Debreceni Fazekas Mihály Gimnázium
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<cassert>
#include<cassert>
#include<unordered_map>
#include<unordered_set>
#include<functional>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<sstream>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<numeric>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define xx first
#define yy second
#define sz(x) (int)(x).size()
#define gc getchar
#define IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mp make_pair
#ifndef ONLINE_JUDGE
# define LOG(x) (cerr << #x << " = " << (x) << endl)
#else
# define LOG(x) ((void)0)
#endif
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const double PI=acos(-1);
template<typename T> T getint() {
T val=0;
char c;
bool neg=false;
while((c=gc()) && !(c>='0' && c<='9')) {
neg|=c=='-';
}
do {
val=(val*10)+c-'0';
} while((c=gc()) && (c>='0' && c<='9'));
return val*(neg?-1:1);
}
int c=0;
struct trie {
vector<pair<int, trie*>> sub;
//trie* sub[26];
short cnt;
trie() {
cerr<<"CREATED"<<c++<<"\n";
cnt=0;
}
};
void insert(trie *root, string& t){
for(auto i:t) {
trie* idx=0;
for(auto j:root->sub) {
if(j.first==i-'a') {
idx=j.second;
}
}
if(idx==0) {
root->sub.push_back({i-'a', new trie()});
idx=root->sub.back().second;
}
root=idx;
}
root->cnt++;
}
int cnt(trie *root, string &t) {
for(auto i:t) {
trie* idx=0;
for(auto j:root->sub) {
if(j.first==i-'a') {
idx=j.second;
}
}
if(idx==0) {
return 0;
}
root=idx;
}
return root->cnt;
}
int hatv[10];
trie *tr[3000];
string t[50001];
int main() {
IO;
hatv[0]=1;
for(int i=1;i<10;++i) hatv[i]=hatv[i-1]*3;
for(int i=0;i<3000;++i) tr[i]=new trie();
int n,k;
cin>>n>>k;
for(int i=0;i<n;++i) {
cin>>t[i];
vector<int> nemk;
for(int j=0;j<k;++j) {
if(t[i][j]!='?') nemk.push_back(j);
}
//for(auto i:nemk) cerr<<i<<" ";
//cerr<<"NEMK\n";
string mm;
for(int j=0;j<(1<<sz(nemk));++j) {
mm.clear();
int mask=0;
for(int l=0;l<sz(nemk);++l) {
if((1<<l)&j) {
mask+=2*hatv[nemk[l]];
mm.push_back(t[i][nemk[l]]);
}else {
mask+=1*hatv[nemk[l]];
}
}
//cerr<<mask<<" ("<<j<<")"<<" -> "<<mm<<" insert\n";
insert(tr[mask], mm);
}
}
ll res=0;
vector<int> kk, nk;
for(int i=0;i<n;++i) {
kk.clear();
nk.clear();
for(int j=0;j<k;++j) {
if(t[i][j]!='?') {
nk.push_back(j);
}
else kk.push_back(j);
}
string nemk;
for(int q=0;q<(1<<sz(nk));++q) {
nemk.clear();
int mask_base=0;
for(int l=0;l<sz(nk);++l) {
if((1<<l)&q) {
mask_base+=hatv[nk[l]]*2;
nemk+=t[i][nk[l]];
}else {
}
}
for(int j=0;j<(1<<sz(kk));++j) {
int mask=mask_base;
for(int l=0;l<sz(kk);++l) {
if((1<<l)&j) {
mask+=hatv[kk[l]];
}
}
//cerr<<mask<<" -> "<<nemk<<" CNT\n";
res+=cnt(tr[mask], nemk);
}
}
}
assert((res-n)%2==0);
cout<<(res-n)/2<<"\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
2168 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
2168 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
2168 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
113 ms |
3420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
95 ms |
3064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
768 ms |
12588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1525 ms |
25760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2775 ms |
45968 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3041 ms |
57920 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3033 ms |
59224 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
