제출 #1238642

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1238642		nlsosad	Genetics (BOI18_genetics)	C++20	0 / 100	1294 ms	6228 KiB

genetics

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, K;
    cin >> n >> m >> K;
    vector<string> s(n);
    for(int i = 0; i < n; i++){
        cin >> s[i];
    }

    // bs[i][c] là bitset độ dài m, đánh dấu các vị trí j mà s[i][j] == letter c
    // đánh index: A→0, C→1, G→2, T→3
    const int MAXM = 4000;
    static bitset<MAXM> bs[4000][4];
    auto idx = [&](char ch){
        if(ch == 'A') return 0;
        if(ch == 'C') return 1;
        if(ch == 'G') return 2;
        return 3;
    };

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            bs[i][ idx(s[i][j]) ].set(j);
        }
    }

    // Thử từng s[i] làm ứng viên
    for(int i = 0; i < n; i++){
        bool ok = true;
        for(int j = 0; j < n; j++){
            if(i == j) continue;
            // tính số vị trí giống nhau giữa s[i] và s[j]
            int same = 0;
            for(int c = 0; c < 4; c++){
                same += (bs[i][c] & bs[j][c]).count();
            }
            int diff = m - same;
            if(diff != K){
                ok = false;
                break;
            }
        }
        if(ok){
            cout << s[i] << "\n";
            return 0;
        }
    }

    // Không tìm được
    cout << -1 << "\n";
    return 0;
}

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