Submission #1130636

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130636		Muhammet	Genetics (BOI18_genetics)	C++20	46 / 100	2093 ms	2548 KiB

genetics

#include "bits/stdc++.h"
 
using namespace std;
 
#define ll long long
#define SZ(s) (int)s.size()
 
int n, m, k1;
 
bitset <4101> st[4101], st1;
 
string s1;
 
int main(){
	ios::sync_with_stdio(false); cin.tie(nullptr);

	cin >> n >> m >> k1;
	if(n > 100){
		for(int i = 1; i <= n; i++){
			cin >> s1;
			for(int j = 0; j < m; j++){
				if(s1[j] == 'A') st[i][j] = 1;
			}
		}
		vector <int> vis(n+1,0);
		for(int i = 1; i <= n; i++){
			bool tr = 0;
			if(vis[i]) continue;
			for(int j = 1; j <= n; j++){
				if(i == j) continue;
				st1 = (st[i] ^ st[j]);
				int cn = st1.count();
				if(cn != k1){
					tr = 1;
					vis[j] = 1;
					break;
				}
			}
			if(!tr){
				cout << i;
				exit(0);
			}
		}
	}
	string s[n+1];
	for(int i = 1; i <= n; i++){
		cin >> s[i];
	}
	for(int i = 1; i <= n; i++){
		bool tr = 0;
		for(int j = 1; j <= n; j++){
			int cnt = 0;
			if(i == j) continue;
			for(int i1 = 0; i1 < m; i1++){
				cnt += (s[i][i1] != s[j][i1]);
			}
			if(cnt != k1){
				tr = 1;
				break;
			}
		}
		if(!tr){
			cout << i;
			exit(0);
		}
	}
}

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