Submission #283513

#	Time	Username	Problem	Language	Result	Execution time	Memory
283513		zecookiez	Genetics (BOI18_genetics)	C++17	100 / 100	301 ms	36552 KiB

genetics

#include <bits/stdc++.h>
using namespace std;
template<class C>constexpr int len(const C&c){return int(c.size());}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MAXN = 4105;
const long long MAXV = 1e14;
long long arr[MAXN], related[MAXN][4];
string S[MAXN];
uniform_int_distribution<long long> rng_range(1, MAXV);
int pos(char c){
    if(c == 'A') return 0;
    if(c == 'C') return 1;
    return c == 'G' ? 2 : 3;
}
int main(){
    cin.sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("haybales.in", "r", stdin);
    //freopen("haybales.out", "w", stdout);
    int n, m; long long k, tot = 0; cin >> n >> m >> k; string s;
    for(int i = 1; i <= n; ++i){
        cin >> S[i]; arr[i] = rng_range(rng);
        tot += arr[i];
        for(int j = 0; j < m; ++j) related[j][pos(S[i][j])] += arr[i];
    }
    for(int i = 1; i <= n; ++i){
        long long tot1, cur = 0;
        for(int j = 0; j < m; ++j){
            tot1 = related[j][0] + related[j][1] + related[j][2] + related[j][3];
            cur += tot1 - related[j][pos(S[i][j])];
        }
        // if mismatch K times, then arr[x] should appear K times aka == K * arr[k].
        if((tot - arr[i]) * k == cur){
            cout << i << '\n'; return 0;
        }
    }
    return 0;
}

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