Submission #444484

#TimeUsernameProblemLanguageResultExecution timeMemory
444484zxcvbnmParametriziran (COCI19_parametriziran)C++14
88 / 110
878 ms65540 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int p = 31; const int mod = 1e9 + 9; ll hsh(const string& s) { ll ret = 0; ll p_pow = 1; for(char c : s) { int ch = 26; if (isalpha(c)) { ch = c - 'a'; } else if (c == '*') { ch = 27; } // cout << c << " " << ch << "\n"; ret = (ret + ch * p_pow) % mod; p_pow = (p_pow * p) % mod; } return ret; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; unordered_map<string, int> cnt; vector<string> a(n); for(int i = 0; i < n; i++) { cin >> a[i]; } for(int i = 0; i < n; i++) { string str = a[i]; for(int mask = 0; mask < (1 << m); mask++) { for(int j = 0; j < m; j++) { if (mask & (1 << j)) { str[j] = '*'; } } cnt[str]++; for(int j = 0; j < m; j++) { if (mask & (1 << j)) { str[j] = a[i][j]; } } } } ll ans = 0; for(string str : a) { vector<int> idx; for(int i = 0; i < m; i++) { if (isalpha(str[i])) { idx.push_back(i); } } int letters = idx.size(); for(char& c : str) { if (c == '?') { c = '*'; } } string str2 = str; for(int mask = 0; mask < (1 << letters); mask++) { for(int j = 0; j < letters; j++) { if (mask & (1 << j)) { str[idx[j]] = '?'; } } ans += cnt[str]; for(int j = 0; j < letters; j++) { if (mask & (1 << j)) { str[idx[j]] = str2[idx[j]]; } } } // cerr << "\n"; } ans -= n; ans /= 2; 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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...