Submission #549850

#	Time	Username	Problem	Language	Result	Execution time	Memory
549850		zxcvbnm	Genetics (BOI18_genetics)	C++14	46 / 100	2044 ms	36428 KiB

genetics

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

constexpr int nax = 4102;

void go(int idx) {
    cout << idx+1 << "\n";
    exit(0);
}

const map<char, int> mp = {
    {'A', 0},
    {'C', 1},
    {'G', 2},
    {'T', 3}
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

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

    int cnt[m][4];
    int cnt_chars[n][4];
    memset(cnt, 0, sizeof cnt);
    memset(cnt_chars, 0, sizeof cnt_chars);

    vector<pair<string, int>> str(n);

    for(int i = 0; i < n; i++) {
        cin >> str[i].first;
        str[i].second = i;
    }

    shuffle(str.begin(), str.end(), rng);

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cnt[j][mp.at(str[i].first[j])]++;
        }
    }

    for(int i = 0; i < n; i++) {
        int diff = 0;
        for(int j = 0; j < m; j++) {
            diff += (n - cnt[j][mp.at(str[i].first[j])]);
        }

//        cout << diff << "\n";
        if (diff != (n-1) * k) continue;

        bool ok = true;
        int curr_diff[n];
        memset(curr_diff, 0, sizeof curr_diff);

        for(int idx = 0; idx < n; idx++) {
            if (idx == i) continue;
            for(int j = 0; j < m; j++) {
                curr_diff[idx] += (str[idx].first[j] != str[i].first[j]);
            }

            if (curr_diff[idx] != k) {
                ok = false;
                break;
            }
        }


        if (ok) {
             go(str[i].second);
        }
    }

    throw;

    return 0;
}

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