oj.uz

Submission #542379

# Submission time Handle Problem Language Result Execution time Memory
542379 2022-03-26T10:06:05 Z the_horo Parametriziran (COCI19_parametriziran) C++17
55 / 110
 3000 ms 22112 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1620 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2516 KB Output is correct
2 Correct 12 ms 4356 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4692 KB Output is correct
2 Correct 10 ms 4180 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 2644 KB Output is correct
2 Correct 160 ms 6156 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 7744 KB Output is correct
2 Correct 1487 ms 6148 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 3604 KB Output is correct
2 Execution timed out 3047 ms 17988 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3043 ms 4856 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 489 ms 2900 KB Output is correct
2 Execution timed out 3074 ms 22112 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3077 ms 2796 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3089 ms 4900 KB Time limit exceeded
2 Halted 0 ms 0 KB -