Submission #1285050

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285050		nguyenkhangninh99	Genetics (BOI18_genetics)	C++20	27 / 100	20 ms	12872 KiB

genetics

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3", "unroll-loops")
#pragma GCC target("avx2", "popcnt")
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;
        vector<vector<int>> val(n, vector<int>(n, -1));
        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) continue;
                if(val[i][j] == -1) val[i][j] = val[j][i] = (bs[i] ^ bs[j]).count();

                if(val[i][j] != k) {
                    valid[i] = valid[j] = false;
                    break;
                };
    		}
    		if(ok == true){
    			cout << ii + 1;
    			return 0;
    		}
    	}
	}
	return 0;
}

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