Submission #689923

#	Time	Username	Problem	Language	Result	Execution time	Memory
689923		NK_	Genetics (BOI18_genetics)	C++17	100 / 100	194 ms	82988 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>;
using ll = long long;

const ll MX = 1e15+7;
int main() {
	cin.tie(0)->sync_with_stdio(0);
	

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

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

	vector<vector<int>> A(N, vector<int>(M));
	vector<array<ll, 4>> C(M, {0, 0, 0, 0});
	vector<ll> W(N);
	for(int i = 0; i < N; i++) {
		str S; cin >> S;
		W[i] = rnd();
		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][j] = c;
			C[j][c] += W[i];
		}
	}

	ll SW = accumulate(begin(W), end(W), 0LL);
	for(int i = 0; i < N; i++) {
		SW -= W[i];

		ll H = 0;
		for(int j = 0; j < M; j++) H += C[j][A[i][j]] - W[i];

		// cout << SW << " " << H << " " << W[i] << nl;

		if (H == (K * SW)) {
			cout << i+1 << nl;
			return 0;
		}

		SW += W[i];
	}



    return 0;
}

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