Submission #689888

#	Time	Username	Problem	Language	Result	Execution time	Memory
689888		NK_	Genetics (BOI18_genetics)	C++17	0 / 100	24 ms	8644 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 < 20; t++) {
		int n = size(ans);
		int I = (rnd() % n);

		vector<int> pos;
		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) pos.push_back(k);
		}

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

		int j = 0;
		vector<int> nans = {};
		for(int i = 0; i < size(pos); i++) if (j < size(ans) && pos[i] == ans[j]) { 
			nans.push_back(pos[i]); j++; 
		}

		ans.swap(nans);
	}

	assert(false);

    return 0;
}

Compilation message (stderr)

genetics.cpp: In function 'int main()':
genetics.cpp:40:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   40 |   if (size(pos) == N-1) {
      |       ~~~~~~~~~~^~~~~~
genetics.cpp:47:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for(int i = 0; i < size(pos); i++) if (j < size(ans) && pos[i] == ans[j]) {
      |                  ~~^~~~~~~~~~~
genetics.cpp:47:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for(int i = 0; i < size(pos); i++) if (j < size(ans) && pos[i] == ans[j]) {
      |                                          ~~^~~~~~~~~~~

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