Submission #1339476

#TimeUsernameProblemLanguageResultExecution timeMemory
1339476po_rag526Parametriziran (COCI19_parametriziran)C++20
66 / 110
1730 ms99644 KiB
#include <bits/stdc++.h>
#pragma GCC optimization("Ofast,unroll-loops")
#pragma GCC optimize("O3")
#pragma GCC target("avx2,popcnt")
using namespace std;

//char ch[6][50001];
map<string, int> fr[64];

int bkt(string s, int poz, int mask, string ss){
    if(poz == s.size()){
        return fr[mask][ss];
    }
    if(s[poz] == '#') return bkt(s, poz + 1, mask, ss);
    if(s[poz] != '?') return bkt(s, poz + 1, mask, ss + s[poz]);
    int ans = 0;
    for(char ch = 'a'; ch <= 'z'; ch++){
        ans += bkt(s, poz + 1, mask, ss + ch);
    }
    return ans;
}

int main(){

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

    int n, m;
    long long ans = 0;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        string s, ss = "";
        cin >> s;
        int mask = 0;
        for(int j = 0; j < m; j++){
            if(s[j] != '?'){
                mask ^= (1 << j);
                ss += s[j];
            }
            else if(ss[j] == '?') ss += '#';
        }
        //cout << "x\n";
        for(int mask2 = 0; mask2 < 1 << m; mask2++){
            string s2 = "";
            for(int j = 0; j < m; j++){
                if((mask2 & (1 << j)) && (mask & (1 << j)))
                    s2 += s[j];
                else if(mask2 & (1 << j))
                    s2 += '?';
                else
                    s2 += '#';
            }
            //cout << mask2 << " " << s2 << " " << fr[mask2][s2] << '\n';
            ans += fr[mask2][s2];
        }
        for(int mask2 = 0; mask2 < 1 << m; mask2++){
            if((mask2 & mask) == mask2){
                string s2 = "";
                for(int j = 0; j < m; j++){
                    if(mask2 & (1 << j)){
                        s2 += s[j];
                    }
                    else if(mask & (1 << j))
                        s2 += '?';
                    else
                        s2 += '#';
                }
                //cout << s << " " << s2 << '\n';
                fr[mask][s2]++;
            }
        }
    }
    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...