Submission #96712

#	Time	Username	Problem	Language	Result	Execution time	Memory
96712		polyfish	Parametriziran (COCI19_parametriziran)	C++14	66 / 110	1374 ms	66560 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define debug(x) {cerr << #x << " = " << x << '\n';}
#define PR(a, n) {cerr << #a << " = "; for (int _=1; _<=n; ++_) cerr << a[_] << ' '; cerr << '\n';}
#define PR0(a, n) {cerr << #a << " = "; for (int _=0; _<n; ++_) cerr << a[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"

const int M = 6;        ///notice
const int MAX_N = 50002;

int n;
string s[MAX_N];
vector<int> p(M);
int64_t res;
map<vector<int>, int> mp;

void readInput() {
    int m;

    cin >> n >> m;

    for (int i=1; i<=n; ++i) {
        cin >> s[i];
        while (s[i].size()<M)
            s[i] += '?';
    }
}

void backtrack1(int idx, int pos) {
    if (s[idx][pos]=='?') {
        p[pos] = -1;
        if (pos==M-1) {
            // PR0(p, p.size());
            res += mp[p];
        }
        else {
            backtrack1(idx, pos+1);
        }
    }
    else {
        for (int i=0; i<2; ++i) {
            p[pos] = (i==0 ? s[idx][pos]-'a' : 26);
            if (pos==M-1) {
                // PR0(p, p.size());
                res += mp[p];
            }
            else {
                backtrack1(idx, pos+1);
            }
        }
    }
}

void backtrack2(int idx, int pos) {
    for (int i=0; i<2; ++i) {
        if (i==0)
            p[pos] = -1;
        else
            p[pos] = (s[idx][pos]=='?' ? 26 : s[idx][pos]-'a');
        if (pos==M-1) {
            // PR0(p, p.size());
            ++mp[p];
        }
        else {
            backtrack2(idx, pos+1);
        }
    }
}

void solve() {
    for (int i=1; i<=n; ++i) {
        backtrack1(i, 0);
        backtrack2(i, 0);
    }

    cout << res;
}

int main() {
    #ifdef GLASSES_GIRL
        freopen(FILE_NAME".inp", "r", stdin);
        freopen(FILE_NAME".out", "w", stdout);
    #endif
    readInput();
    solve();
}

• 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: 0 / 11
• Subtask 8: 0 / 11
• Subtask 9: 0 / 11
• Subtask 10: 0 / 11