Submission #676883

#	Time	Username	Problem	Language	Result	Execution time	Memory
676883		Cyanmond	Genetics (BOI18_genetics)	C++17	27 / 100	2069 ms	3100 KiB

genetics

#include <bits/stdc++.h>

std::clock_t start_time;
double get_sec() {
    return (std::clock() - start_time) * 1000 / CLOCKS_PER_SEC;
}

int main() {
    start_time = std::clock();
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N, M, K;
    std::cin >> N >> M >> K;
    std::vector<std::string> S(N);
    for (auto &e : S) {
        std::cin >> e;
    }

    std::vector<bool> ok(N, true);
    std::mt19937 mt(100);
    std::uniform_int_distribution dist(0, N - 1);
    while (get_sec() < 1500) {
        const int a = dist(mt);
        const int b = dist(mt);
        if (a == b) {
            continue;
        }

        int cnt = 0;
        for (int i = 0; i < M; ++i) {
            if (S[a][i] != S[b][i]) {
                ++cnt;
            }
        }
        if (cnt != K) {
            ok[a] = false;
            ok[b] = false;
        }
    }

    for (int i = 0; i < N; ++i) {
        if (not ok[i]) {
            continue;
        }
        for (int j = 0; j < N; ++j) {
            if (i == j) {
                continue;
            }
            int cnt = 0;
            for (int k = 0; k < M; ++k) {
                if (S[i][k] != S[j][k]) {
                    ++cnt;
                }
            }
            if (cnt != K) {
                ok[i] = false;
                ok[j] = false;
                break;
            }
        }

        if (ok[i]) {
            std::cout << i + 1 << std::endl;
            break;
        }
    }
}

• Subtask 1: 27 / 27
• Subtask 2: 0 / 19
• Subtask 3: 0 / 28
• Subtask 4: 0 / 26