Submission #953597

#	Time	Username	Problem	Language	Result	Execution time	Memory
953597		Sharky	Genetics (BOI18_genetics)	C++17	100 / 100	446 ms	36616 KiB

genetics

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

#define int long long
const int mod = (1LL << 31) - 1;

mt19937 rng((int) chrono::steady_clock::now().time_since_epoch().count());

int rnd(int u, int v) {
    return uniform_int_distribution<int> (u, v) (rng);
}

int cv(char x) {
    if (x == 'A') return 0;
    if (x == 'C') return 1;
    if (x == 'G') return 2;
    return 3;
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m, diff;
    cin >> n >> m >> diff;
    vector<int> w(n);
    vector<vector<int>> c(m, vector<int> (4, 0));
    vector<string> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        w[i] = rnd(1, (1LL << 31) - 2);
        for (int j = 0; j < m; j++) c[j][cv(a[i][j])] = (c[j][cv(a[i][j])] + w[i]) % mod;
    }
    for (int i = 0; i < n; i++) {
        int wc = 0, sum = 0;
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            sum = (sum + w[j]) % mod;
        }
        sum = (sum * diff) % mod;
        for (int j = 0; j < m; j++) {
            for (int k = 0; k < 4; k++) if (cv(a[i][j]) != k) wc = (wc + c[j][k]) % mod;
        }
        if (sum != wc) continue;
        cout << i + 1 << '\n';
        return 0;
    }
}

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