Submission #1285040

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285040		nguyenkhangninh99	Genetics (BOI18_genetics)	C++20	0 / 100	305 ms	4348 KiB

genetics

#include <bits/stdc++.h>
using namespace std;
bitset<4100> bs[4100];
string t[4100];
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){
    			i;
    			return 0;
    		}
    	}
    }else{
    	vector<int> valid(n, true);
    	for(int i = 0; i < n; i++){
    		if(valid[i] == false) continue;
    		bool ok = true;
    		for(int j = 0; j < n; j++){
    			if(i != j) ok &= ((bs[i] ^ bs[j]).count() == k);
    			if(ok == false){
    				valid[j] = false;
    				break;
				}
    		}
    		if(ok == true){
    			i;
    			return 0;
    		}
    	}
	}
	return 0;
}

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