Submission #857283

#	Time	Username	Problem	Language	Result	Execution time	Memory
857283		biank	Genetics (BOI18_genetics)	C++17	46 / 100	2051 ms	31872 KiB

genetics

#include <bits/stdc++.h>

using namespace std;

#define SIZE(x) (int)x.size()
#define ALL(x) x.begin(), x.end()

typedef long long ll;
typedef vector <int> vi;
typedef pair <int, int> ii;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	map <char, int> m = {{'A', 0}, {'C', 1}, {'G', 2}, {'T', 3}};
	
	int N, M, K;
	cin >> N >> M >> K;
	
	vector <string> S(N);
	vector <vi> count(4, vi(M, 0));
	
	for (int i=0; i<N; i++) {
		cin >> S[i];
		for (int j=0; j<M; j++) {
			int k = m[S[i][j]];
			count[k][j]++;
		}
	}
	
	int ans = -1;
	for (int i=0; i<N; i++) {
		ll diff = 0;
		for (int j=0; j<M; j++) {
			int k = m[S[i][j]];
			diff += N - count[k][j];
		}
		if (diff != (N-1)*K) continue;
		
		bool flag = false;
		for (int j=0; j<N; j++) {
			if (i == j) continue;
			diff = 0;
			for (int k=0; k<M; k++) {
				diff += (S[i][k] != S[j][k]);
			}
			if (diff != K) {
				flag = true;
				break;
			}
		}
		if (!flag) {
			ans = i+1;
			break;
		}
	}
	
	cout << ans << '\n';
	return 0;
}

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