Submission #1285044

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285044		nguyenkhangninh99	Genetics (BOI18_genetics)	C++20	46 / 100	2094 ms	21916 KiB

genetics

#include <bits/stdc++.h>
using namespace std;
bitset<4100> bs[4100];
string t[4100];
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

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

    for(int i = 1; i <= n; i++){
      cin >> t[i - 1];
  		for(int j = 0; j < m; j++){
  			if(t[i - 1][j] == 'A') bs[i - 1][j] = 1;
  		}
    }
    if(n <= 100 && m <= 100){
    	for(int i = 0; i < n; i++){
    		bool ok = true;
    		for(int j = 0; j < n; j++){
    			if(j == i) continue;
    			int cnt = 0;
    			for(int l = 0; l < m; l++) if(t[i][l] != t[j][l]) cnt++;
    			ok &= (cnt == k);
    			if(ok == false) break;
    		}
    		if(ok == true){
    			cout << i + 1;
    			return 0;
    		}
    	}
    }else{
    	vector<int> valid(n, true);
        vector<int> order(n);
        for(int i = 0; i < n; i++) order[i] = i;
        shuffle(order.begin(), order.end(), rng);
    	for(int i = 0; i < n; i++){
            int ii = order[i];
    		if(valid[ii] == false) continue;
    		bool ok = true;
    		for(int j = 0; j < n; j++){
                int jj = order[j];
    			if(ii != jj) ok &= ((bs[ii] ^ bs[jj]).count() == k);
    			if(ok == false){
    				valid[jj] = false;
    				break;
				}
    		}
    		if(ok == true){
    			cout << ii + 1;
    			return 0;
    		}
    	}
	}
	return 0;
}

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