Submission #1284556

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284556		Pannda	Genetics (BOI18_genetics)	C++20	100 / 100	283 ms	17264 KiB

genetics

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    auto rand = [&](long long n) {
        return uniform_int_distribution<long long>(0, n - 1)(rng);
    };

    int n, m, k;
    cin >> n >> m >> k;

    vector<long long> hn(n);
    long long all_k = 0;
    for (int i = 0; i < n; i++) {
        hn[i] = rand(1LL << 62);
        all_k += k * hn[i];
    }

    auto convert = [&](char c) -> int {
        if (c == 'A') return 0;
        if (c == 'T') return 1;
        if (c == 'G') return 2;
        if (c == 'C') return 3;
        return -1;
    };

    vector<string> str(n);
    vector<array<long long, 4>> mp(m, array<long long, 4>{});
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < m; j++) {
            int c = convert(s[j]);
            mp[j][c] += hn[i];
        }
        str[i] = s;
    }

//    for i in n:
//        for j in m:
//            identify those strings that differs in this char, let the mask be [0, 1, 1, 0, 0, 1, 0] (size n)
//        if summing of those mask becomes [K, K, K, 0, K, K] (size n, 0 is at i)
//            then win

    for (int i = 0; i < n; i++) {
        long long sum = 0;
        for (int j = 0; j < m; j++) {
            int c = convert(str[i][j]);
            for (int nc = 0; nc < 4; nc++) if (nc != c) {
                sum += mp[j][nc];
            }
        }
        long long expect_sum = all_k - k * hn[i];
        if (sum == expect_sum) {
            cout << i + 1 << '\n';
            break;
        }
    }

}

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