제출 #1286479

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286479		nguyenkhangninh99	Genetics (BOI18_genetics)	C++20	100 / 100	378 ms	132820 KiB

genetics

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

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

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n, m, k; cin >> n >> m >> k;

    vector<int> h(n);
    
    int allk = 0;
    for(int i = 0; i < n; i++){
        h[i] = uniform_int_distribution<int>(0, (1ll << 62))(rng);
        allk += k * h[i];
    }

    vector<vector<int>> s(n, vector<int>(m));
    vector<array<int, 4>> mp(m, array<int, 4>{});
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            char x; cin >> x;
            s[i][j] = (x == 'A' ? 0 : (x == 'T' ? 1 : (x == 'G' ? 2 : 3)));
            mp[j][s[i][j]] += h[i];
        }
    }


    for(int i = 0; i < n; i++){
        int sum = 0;
        for(int j = 0; j < m; j++){
            for(int c = 0; c < 4; c++) if(c != s[i][j]) sum += mp[j][c];
        }
        if(sum == allk - k * h[i]){
            cout << i + 1;
            return 0;
        }
    }
}

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