Submission #689897

#	Time	Username	Problem	Language	Result	Execution time	Memory
689897		NK_	Genetics (BOI18_genetics)	C++17	27 / 100	2078 ms	4180 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 nax = 4105;
using B = bitset<nax>;

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

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

	vector<vector<B>> A(N, vector<B>(4));
	for(int i = 0; i < N; i++) {
		str S; cin >> S;
		for(int j = 0; j < M; j++) {
			int c = -1;
			if (S[j] == 'A') c = 0;
			if (S[j] == 'G') c = 1;
			if (S[j] == 'C') c = 2;
			if (S[j] == 'T') c = 3;
			A[i][c][j] = 1;
		}
	}

	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 same = 0;
			for(int c = 0; c < 4; c++) same += (A[I][c] & A[k][c]).count();
			int c = M - same;
			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