oj.uz

Submission #636729

# Submission time Handle Problem Language Result Execution time Memory
636729 2022-08-30T01:03:16 Z iee Parametriziran (COCI19_parametriziran) C++17
110 / 110
 1805 ms 44372 KB 
// 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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1876 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1876 KB Output is correct
2 Correct 13 ms 1988 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2016 KB Output is correct
2 Correct 30 ms 2048 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 2632 KB Output is correct
2 Correct 35 ms 2256 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 2488 KB Output is correct
2 Correct 83 ms 3016 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 6892 KB Output is correct
2 Correct 71 ms 2232 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 513 ms 11404 KB Output is correct
2 Correct 99 ms 2132 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 711 ms 19480 KB Output is correct
2 Correct 450 ms 9900 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1110 ms 29884 KB Output is correct
2 Correct 211 ms 2380 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1805 ms 44372 KB Output is correct
2 Correct 1156 ms 22768 KB Output is correct