Submission #542379

#	Time	Username	Problem	Language	Result	Execution time	Memory
542379		the_horo	Parametriziran (COCI19_parametriziran)	C++17	55 / 110	3089 ms	22112 KiB

Main

#include <bits/stdc++.h>


/* Defines */
using u64 = uint64_t;

constexpr size_t MAX_CHARS = 6;


/* Function definitions */
void readInput();
u64 countPairs(const std::vector<size_t> &sourse, const size_t indexToCheck);


/* Global variables */
std::vector<std::array<char, MAX_CHARS + 1>> input;


/* Function declarations */
void readInput () {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    size_t wordCount, letterCount;
    std::cin >> wordCount >> letterCount;

    input.resize(wordCount);

    for (auto &word: input)
        std::cin >> word.data();

    std::ios_base::sync_with_stdio(true);
    std::cin.tie(&std::cout);
}

u64 countPairs (const std::vector<size_t> &source, const size_t indexToCheck) {
    static constexpr std::array<char, 26> alphabet = {
        'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k',
        'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v',
        'w', 'x', 'y', 'z'
    };

    if (input[0][indexToCheck] == '\0') {
        const u64 count = static_cast<u64>(source.size());
        return count * (count - 1) / 2;
    }

    if (source.size() < 2)
        return 0;

    std::array<std::vector<size_t>, 'z' + 1> prefixes;
    static_assert(prefixes.size() > '?', "Internal asumption error");

    for (auto inputIndex: source) {
        const char c = input[inputIndex][indexToCheck];

        if ('a' <= c && c <= 'z')
            prefixes[c].emplace_back(inputIndex);
        else if (c == '?') {
            prefixes['?'].emplace_back(inputIndex);
            for (char i: alphabet)
                prefixes[i].emplace_back(inputIndex);
        } else
            assert(false);
    }

    const u64 falsePairs = countPairs(prefixes['?'], indexToCheck + 1);

    u64 result = 0;
    for (const char c: alphabet)
        if (prefixes[c].size() >= 1 + prefixes['?'].size()) {
            result += countPairs(prefixes[c], indexToCheck + 1) - falsePairs;
        }

    return result + falsePairs;
}


int main () {
    readInput();

    std::vector<size_t> allIndexes(input.size());
    std::iota(allIndexes.begin(), allIndexes.end(), 0);

    std::cout << countPairs(allIndexes, 0) << '\n';
}

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