Submission #598395

#	Time	Username	Problem	Language	Result	Execution time	Memory
598395		KoD	Genetics (BOI18_genetics)	C++17	100 / 100	475 ms	33692 KiB

genetics

#include <bits/stdc++.h>

using u64 = std::uint64_t;
using u128 = __uint128_t;

constexpr u64 mod = ((u64)1 << 61) - 1;

struct Fp {
    u64 x;
    Fp(const u64 x = 0) : x(x) {}
    Fp& operator+=(const Fp& t) {
        x += t.x;
        if (x >= mod) x -= mod;
        return *this;
    }
    Fp& operator-=(const Fp& t) {
        if (x < t.x) x += mod;
        x -= t.x;
        return *this;
    }
    Fp operator*(const Fp& t) const {
        const u128 a = (u128)x * t.x;
        const u64 b = (a >> 61) + (a & mod);
        return b >= mod ? b - mod : b;
    }
};

using std::vector;
using std::array;

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, M, K;
    std::cin >> N >> M >> K;
    vector<Fp> W(N);
    vector S(N, vector<char>(M));
    std::default_random_engine engine(0xABCDEF);
    std::uniform_int_distribution<u64> rand(0, mod - 1);
    vector<array<Fp, 4>> sum(M);
    for (int i = 0; i < N; ++i) {
        W[i] = rand(engine);
        for (int j = 0; j < M; ++j) {
            char c;
            std::cin >> c;
            if (c == 'A') S[i][j] = 0;
            if (c == 'C') S[i][j] = 1;
            if (c == 'G') S[i][j] = 2;
            if (c == 'T') S[i][j] = 3;
            sum[j][S[i][j]] += W[i];
        }
    }
    Fp wsum = 0;
    for (int i = 0; i < N; ++i) {
        wsum += W[i];
    }
    for (int i = 0; i < N; ++i) {
        Fp dif = wsum * (M - K);
        for (int j = 0; j < M; ++j) {
            dif -= sum[j][S[i][j]];
        }
        dif += W[i] * K;
        if (dif.x == 0) {
            std::cout << i + 1 << '\n';
            break;
        }
    }
    return 0;
}

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