Submission #875628

#	Time	Username	Problem	Language	Result	Execution time	Memory
875628		vjudge1	Genetics (BOI18_genetics)	C++17	100 / 100	917 ms	36508 KiB

genetics

// https://oj.uz/problem/view/BOI18_genetics

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

mt19937 rng(123);

int32_t main() {
        ios_base::sync_with_stdio(0);
        cin.tie(0);

        int n, m, k;
        cin >> n >> m >> k;
        vector<string> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        vector<int> x(n);
        for (int i = 0; i < n; i++) x[i] = rng() % (int)(1e9 + 7);
        map<char, int> mp;
        mp['A'] = 0, mp['T'] = 1, mp['C'] = 2, mp['G'] = 3;
        vector<int64_t> sum(n);
        for (int i = 0; i < m; i++) {
                vector<int64_t> cnt(4, 0);
                for (int j = 0; j < n; j++) cnt[mp[a[j][i]]] += x[j];
                for (int j = 0; j < n; j++) {
                        for (int k = 0; k < 4; k++) {
                                if (mp[a[j][i]] == k) continue;
                                sum[j] += cnt[k];
                        }
                }
        }
        int64_t sum_all = accumulate(x.begin(), x.end(), 0ll);
        for (int i = 0; i < n; i++) {
                if (sum[i] == 1ll * (sum_all - x[i]) * k) return cout << i + 1, 0;
        }
}

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