Submission #857300

#	Time	Username	Problem	Language	Result	Execution time	Memory
857300		biank	Genetics (BOI18_genetics)	C++14	46 / 100	2070 ms	21340 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 <pair <string, int>> S(N);
	for (int i=0; i<N; i++) {
		cin >> S[i].first;
		S[i].second = i+1;
	}
	srand(time(0));
	random_shuffle(ALL(S));
	
	int T = (int)ceil(sqrt(N));
	
	vector <vi> count[4];
	for (int i=0; i<4; i++) { 
		count[i].assign(T, vi(M, 0));
	}
	
	vi cant(T, 0);
	
	for (int i=0; i<N; i++) {
		cant[i/T]++;
		for (int j=0; j<M; j++) {
			int k = m[S[i].first[j]];
			count[k][i/T][j]++;
		}
	}
	
	int ans = -1;
	for (int i=0; i<N; i++) {
		bool flag = false;
		for (int j=0; j<T; j++) {
			ll diff = 0;
			for (int k=0; k<M; k++) {
				int C = m[S[i].first[k]];
				diff += cant[j] - count[C][j][k];
			}
			
			if (diff != K * (cant[j] - (i/T == j))) {
				flag = true;
				break;
			}
			
		}
		
		if (flag) continue;
		
		for (int j=0; j<N; j++) {
			if (i == j) continue;
			ll diff = 0;
			for (int k=0; k<M; k++) {
				diff += (S[i].first[k]!= S[j].first[k]);
			}
			if (diff != K) {
				flag = true;
				break;
			}
		}
		
		if (!flag) {
			ans = S[i].second;
			break;
		}
	}
	
	cout << ans << '\n';
	return 0;
}

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