Submission #1339472

#TimeUsernameProblemLanguageResultExecution timeMemory
1339472IanisParametriziran (COCI19_parametriziran)C++17
110 / 110
1116 ms57656 KiB
#include <bits/stdc++.h>

using namespace std;

const int CINCO = 5;
const int SEIS = 6;
const int SIETE = 7;

int n, m;
map<int, uint16_t> fr[1 << SEIS];

void read() {
   cin >> n >> m;
}

int make_hash(char s[], int m) {
   int mask = 0;
   for (int i = 0; i < m; i++) {
      int val = 0;
      if (s[i] != '?') val = s[i] - 'a' + 1;
      mask |= val << (i * CINCO);
   }
   return mask;
}

inline int hash_replace(int mask, int pos, int val) {
   return (mask & ~(((1 << CINCO) - 1) << (pos * CINCO))) | (val << (pos * CINCO));
}

int query(char a[]) {
   int qmask = 0, cnt = 0, len = 0;
   char s[SIETE] = {0};
   for (int i = 0; i < m; i++) {
      if (a[i] == '?') {
         qmask |= 1 << i;
      } else {
         s[len++] = a[i];
      }
   }

   for (int mask = 0; mask < 1 << len; mask++) {
      int h = make_hash(s, len);
      for (int i = 0; i < len; i++) {
         if (mask & (1 << i)) {
            h = hash_replace(h, i, 0);
         }
      }
      if (auto it = fr[qmask].find(h); it != fr[qmask].end()) {
         cnt += it->second;
      }
   }

   return cnt;
}

void update(char a[]) {
   for (int mask = 0; mask < 1 << m; mask++) {
      char s[SEIS];
      int len = 0;
      for (int i = 0; i < m; i++) {
         if (!((mask >> i) & 1)) {
            s[len++] = a[i];
         }
      }
      fr[mask][make_hash(s, len)]++;
   }
}

signed main() {
#ifdef LOCAL
   freopen("input.txt", "r", stdin);
#endif

   ios_base::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);

   cin >> n >> m;
   char a[SIETE];
   int ans = 0;
   for (int i = 1; i <= n; i++) {
      cin >> a;
      ans += query(a);
      update(a);
   }
   cout << ans << '\n';

   return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...