Submission #676895

#	Time	Username	Problem	Language	Result	Execution time	Memory
676895		Cyanmond	Genetics (BOI18_genetics)	C++17	100 / 100	337 ms	36416 KiB

genetics

#include <bits/stdc++.h>

using i64 = long long;

constexpr i64 P = (1ll << 61) - 1;

void add(i64 &a, i64 b) {
    a += b;
    if (a >= P) {
        a -= P;
    }
}

int main() {
    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<i64> H(N);
    std::mt19937 mt(100);
    std::uniform_int_distribution<i64> dist(0, P - 1);
    for (auto &e : H) {
        e = dist(mt);
    }

    std::vector<std::array<i64, 4>> hl(M, {0, 0, 0, 0});

    auto get_id = [&](char x) {
        if (x == 'A') return 0;
        if (x == 'C') return 1;
        if (x == 'G') return 2;
        return 3;
    };

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            add(hl[j][get_id(S[i][j])], H[i]);
        }
    }

    for (int i = 0; i < N; ++i) {
        i64 sum = 0;
        for (int j = 0; j < M; ++j) {
            const int v = get_id(S[i][j]);
            for (int x = 0; x < 4; ++x) {
                if (x == v) {
                    continue;
                }
                add(sum, hl[j][x]);
            }
        }
        
        i64 exp = 0;
        for (int j = 0; j < N; ++j) {
            if (i == j) {
                continue;
            }
            add(exp, H[j]);
        }
        exp = (i64)(__int128_t(exp) * __int128_t(K) % __int128_t(P));

        if (exp == sum) {
            std::cout << i + 1 << std::endl;
            break;
        }
    }
}

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