Submission #917105

#	Time	Username	Problem	Language	Result	Execution time	Memory
917105		406	Genetics (BOI18_genetics)	C++17	100 / 100	83 ms	36396 KiB

genetics

#include <bits/stdc++.h>
#define int int64_t
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)

using namespace std;
using ar = array<int, 2>;

const int64_t INF = 1ll << 60;
const int N = 4200;
int n, m, k, w[N], dp[N][4];
string s[N];

int T(char c) {
        switch (c) { 
                case 'A': 
                        return 0;
                case 'C':
                        return 1;
                case 'G': 
                        return 2;
                case 'T':
                        return 3;
        }
        return -1;
}


signed main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr); 
        cin >> n >> m >> k;
        FOR (i, 0, n)
                cin >> s[i];
        mt19937 rng((int64_t) new char);
        FOR(i, 0, n)
                w[i] = rng();
        int sum = accumulate(w, w + n, 0ll);

        FOR(i, 0, n) {
                FOR(j, 0, m) 
                        dp[j][T(s[i][j])] += w[i];
        }

        FOR(i, 0, n) {
                int ans = 0;
                FOR(j, 0, m) ans += sum - dp[j][T(s[i][j])];
                if (ans == k * (sum - w[i])) {
                        cout << i + 1;
                        return 0;
                }
        }
        assert(false);
        return 0;
}

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