Submission #689896

#	Time	Username	Problem	Language	Result	Execution time	Memory
689896		NK_	Genetics (BOI18_genetics)	C++17	27 / 100	2048 ms	6780 KiB

genetics

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

using str = string;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MOD = 1e9+7;
int main() {
	cin.tie(0)->sync_with_stdio(0);
	

	int N, M, K; cin >> N >> M >> K;

	vector<str> A(N); for(auto& x : A) cin >> x;

	vector<int> ans(N); iota(begin(ans), end(ans), 0);

	auto rnd = [&]() {
		return (rng() * 1LL * rng()) % MOD;
	};

	for(int t = 0; ; t++) {
		set<int> in(begin(ans), end(ans));
		int n = size(ans);
		// cout << n << endl;
		int I = ans[rnd() % n];
		// cout << I << endl;

		int W = 0;
		vector<int> nans;
		for(int k = 0; k < N; k++) {
			int c = 0;
			for(int j = 0; j < M; j++) {
				if (A[k][j] != A[I][j]) c++;
			}
			if (c == K) {
				W++;
				if (in.count(k)) nans.push_back(k);
			}
		}

		if (W == N-1) {
			cout << I+1 << nl;
			return 0;
		}

		ans.swap(nans);
	}

	assert(false);

    return 0;
}

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