Submission #127558

#	Time	Username	Problem	Language	Result	Execution time	Memory
127558		mechfrog88	Genetics (BOI18_genetics)	C++14	27 / 100	28 ms	3832 KiB

genetics

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
using namespace __gnu_pbds;
using namespace std;
 
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef long long ll;
typedef long double ld;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n,m,k;
	cin >> n >> m >> k;
	vector <string> arr(n);
	bitset<4101> s[n];
	for (int z=0;z<n;z++){
		cin >> arr[z];
		for (int x=0;x<m;x++){
			if (arr[z][x] == 'A') s[z][x] = 1;
			else s[z][x] = 0;
		}
	}
	if (n <= 100){
		for (int z=0;z<n;z++){
			bool ok = true;
			for (int x=0;x<n;x++){
				if (z == x) continue;
				ll c = 0;
				for (int q=0;q<m;q++){
					if (arr[z][q] != arr[x][q]) c++;
				}
				if (c != k){
					ok = false;
					break;
				}
			}
			if (ok){
				cout << z+1 << endl;
				return 0;
			}
		}
	} else {
		vector <bool> cannot(n,false);
		for (int z=0;z<n;z++){
			bool ok = true;
			if (cannot[z]) continue;
			for (int x=0;x<n;x++){
				if (cannot[x]) continue;
				if (z == x) continue;
				bitset <4101> temp;
				temp = s[z]^s[x];
				ll c = temp.count();
				if (c != k){
					cannot[x] = true;
					cannot[z] = true;
					ok = false;
					break;
				}
			}
			if (ok){
				cout << z+1 << endl;
				return 0;
			}
		}
	}
	
}

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