Submission #127574

#	Time	Username	Problem	Language	Result	Execution time	Memory
127574		mechfrog88	Genetics (BOI18_genetics)	C++14	46 / 100	2088 ms	19060 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;

inline int readInt() {
    int x=0; char ch=getchar_unlocked(); bool s=1;
    while(ch<'0'||ch>'9'){if(ch=='-')s=0;ch=getchar_unlocked();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar_unlocked();}
    return s?x:-x;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n,m,k;
	n = readInt();
	m = readInt();
	k = readInt();
	vector <vector<char>> arr(n,vector<char>(m));
	bitset<4101> s[n];
	for (int z=0;z<n;z++){
		for (int x=0;x<m;x++){
			int temp = getchar_unlocked();
			if (isspace(temp)){
				arr[z][x] = getchar_unlocked();
			}
			else arr[z][x] = char(temp);
			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 (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: 19 / 19
• Subtask 3: 0 / 28
• Subtask 4: 0 / 26