Submission #636729

#	Time	Username	Problem	Language	Result	Execution time	Memory
636729		iee	Parametriziran (COCI19_parametriziran)	C++17	110 / 110	1805 ms	44372 KiB

Main

// iee
#include <bits/stdc++.h>

#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)
#define fi first
#define se second
using ll = long long;
using ull = unsigned long long;
using namespace std;
void work(int);

template <class T> void read(T &x) {
  x = 0;
  int f = 1, ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + (ch - '0');
    ch = getchar();
  }
  x *= f;
}

int main() {
  int TT = 1; // cin >> TT;
  rep(CAS, 1, TT)
    work(CAS);
  return 0;
}
const int N = 5e4 + 5, base = 28;
string s[N];
int n, m;
ll ans;
map<int, int> cnt;
void work(int CASE) {
  read(n), read(m);
  rep(i, 1, n) {
    cin >> s[i];
    rep(j, 0, (1 << m) - 1) {
      bool ok = 1;
      rep(k, 0, m - 1) {
        if (j >> k & 1) ok &= (s[i][k] != '?');
      }
      if (!ok) continue;
      int h = 0;
      rep(k, 0, m - 1) if (j >> k & 1) h = h * base + 26;
      else if (s[i][k] == '?') h = h * base + 27;
      else h = h * base + (s[i][k] - 'a');
      cnt[h]++;
    }
  }
  rep(i, 1, n) {
    rep(j, 0, (1 << m) - 1) {
      int h = 0;
      rep(k, 0, m - 1) if (j >> k & 1) {
        if (s[i][k] != '?') h = h * base + 27;
        else h = h * base + 26;
      } else if (s[i][k] == '?') h = h * base + 27; else h = h * base + (s[i][k] - 'a');
      if (cnt.find(h) != cnt.end()) ans += cnt[h];
    }
  }
  cout << (ans - n) / 2;
}

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 11 / 11
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 11 / 11
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11