Submission #521649

#	Time	Username	Problem	Language	Result	Execution time	Memory
521649		sofapuden	Genetics (BOI18_genetics)	C++14	100 / 100	528 ms	36700 KiB

genetics

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n, m, K; cin >> n >> m >> K;
	vector<pair<string,int>> v(n);
	int cnt = 1;
	for(auto &x : v)cin >> x.first, x.second = cnt++;
	random_shuffle(v.begin(),v.end());
	random_shuffle(v.begin(),v.end());
	random_shuffle(v.begin(),v.end());
	vector<int> no(n,0);
	vector<vector<int>> sta(m,vector<int>(26,0));
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < m; ++j){
			sta[j][v[i].first[j]-'A']++;
		}
	}
	for(int i = 0; i < n; ++i){
		int cn = 0;
		for(int j = 0; j < m; ++j){
			cn+=sta[j][v[i].first[j]-'A'];
		}
		cn-=m;
		if(cn != (n-1)*(m-K))no[i] = 1;
	}
	for(int i = 0; i < n; ++i){
		if(no[i])continue;
		for(int j = i+1; j < n; ++j){
			int cn = 0;
			for(int k = 0; k < m; ++k){
				if(v[i].first[k] != v[j].first[k])cn++;
			}
			if(cn != K){no[j] = 1, no[i] = 1;break;}
		}
		if(no[i])continue;
		for(int j = 0; j < i; ++j){
			int cn = 0;
			for(int k = 0; k < m; ++k){
				if(v[i].first[k] != v[j].first[k])cn++;
			}
			if(cn != K){no[j] = 1, no[i] = 1;break;}
		}
		if(!no[i]){
			cout << v[i].second << '\n';
			return 0;
		}
	}
}

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