Submission #895652

#	Time	Username	Problem	Language	Result	Execution time	Memory
895652		pcc	Genetics (BOI18_genetics)	C++14	46 / 100	2029 ms	60244 KiB

genetics

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt")

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const int mxn = 4140;
int arr[mxn][mxn];
int N,M,K;
vector<int> v,cand;
const int magic = 5;
bitset<mxn> in;
const int lim = 1.95*CLOCKS_PER_SEC;
int st;

int dif(int a,int b){
	int re = 0;
	for(int i = 0;i<M;i++){
		re += (arr[a][i] != arr[b][i]);
	}
	return re;
}

void collect(){
	for(int i = 0;i<N;i++){
		for(int j = i+1;j<N;j++){
			if(dif(i,j) != K){
				if(!in[i])v.push_back(i);
				if(!in[j])v.push_back(j);
				in[i] = in[j] = true;
			}
		}
		if(!in[i]){
			cout<<i+1;
			exit(0);
		}
	}
	return;
}

int main(){
	st = clock();
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>M>>K;
	for(int i = 0;i<N;i++){
		for(int j = 0;j<M;j++){
			char c;
			cin>>c;
			arr[i][j] = c-'A';
		}
	}
	collect();
	for(int i = 0;i<N;i++){
		if(in[i])continue;
		bool flag = true;
		for(auto &j:v){
			if(dif(i,j) != K)flag = false;
		}
		if(flag)cand.push_back(i);
	}
	assert(cand.size()<100);
	for(auto &i:cand){
		bool flag = true;
		for(int j = 0;j<N;j++){
			if(i == j)continue;
			if(dif(i,j) != K){
				flag = false;
				break;
			}
		}
		if(flag){
			cout<<i+1;
			return 0;
		}
	}
	assert(false);
}

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