Submission #397798

#	Time	Username	Problem	Language	Result	Execution time	Memory
397798		KoD	Genetics (BOI18_genetics)	C++17	100 / 100	970 ms	34552 KiB

genetics

#include <bits/stdc++.h>

using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;

class rep {
    struct Iter {
        usize itr;
        constexpr Iter(const usize pos) noexcept : itr(pos) {}
        constexpr void operator++() noexcept { ++itr; }
        constexpr bool operator!=(const Iter& other) const noexcept {
            return itr != other.itr;
        }
        constexpr usize operator*() const noexcept { return itr; }
    };
    const Iter first, last;

  public:
    explicit constexpr rep(const usize first, const usize last) noexcept
        : first(first), last(std::max(first, last)) {}
    constexpr Iter begin() const noexcept { return first; }
    constexpr Iter end() const noexcept { return last; }
};

u64 xorshift() {
    static u64 state =
        std::chrono::system_clock::now().time_since_epoch().count();
    state ^= state << 7;
    state ^= state >> 9;
    return state;
}

template <class T> T rand_int(const T& min, const T& max) {
    static std::default_random_engine gen(xorshift());
    return std::uniform_int_distribution<T>(min, max)(gen);
}

template <class T> using Vec = std::vector<T>;

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

constexpr u64 SUM(const u64 x, const u64 y) {
    const u64 t = x + y;
    return t >= MOD ? t - MOD : t;
}

constexpr u64 DIF(const u64 x, const u64 y) {
    const u64 t = x + MOD - y;
    return t >= MOD ? t - MOD : t;
}

constexpr u64 PROD(const u64 x, const u64 y) {
    u128 t = (u128)x * y;
    t = (t >> 61) + (t & MOD);
    return t >= MOD ? t - MOD : t;
}

void BOI18_Genetics_main() {
    usize N, M, K;
    std::cin >> N >> M >> K;
    Vec<Vec<char>> S(N, Vec<char>(M));
    for (auto& v : S) {
        for (auto& x : v) {
            std::cin >> x;
        }
    }
    Vec<u64> W(N);
    u64 whole = 0;
    for (auto& x : W) {
        x = rand_int<u64>(1, MOD - 1);
        whole = SUM(whole, x);
    }
    Vec<std::map<char, u64>> sum(M);
    for (const auto i : rep(0, N)) {
        for (const auto j : rep(0, M)) {
            auto& val = sum[j][S[i][j]];
            val = SUM(val, W[i]);
        }
    }
    for (const auto i : rep(0, N)) {
        u64 acc = PROD(whole, M);
        for (const auto j : rep(0, M)) {
            acc = DIF(acc, sum[j][S[i][j]]);
        }
        if (acc == PROD(DIF(whole, W[i]), K)) {
            std::cout << i + 1 << '\n';
            return;
        }
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    BOI18_Genetics_main();
    return 0;
}

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