Submission #56293

#	Time	Username	Problem	Language	Result	Execution time	Memory
56293		model_code	Genetics (BOI18_genetics)	C++17	100 / 100	737 ms	225784 KiB

genetics

#include <iostream>
#include <cstdlib>
#include <cassert>
#include <string>
#include <vector>
using namespace std;

#define trav(a, x) for (auto& a : x)

int main() {
	cin.sync_with_stdio(false);
	int N, M, K;
	cin >> N >> M >> K;
	vector<string> input(N);
	for (int i = 0; i < N; ++i) cin >> input[i];
	bool expand = false;
	trav(x, input) trav(y, x) {
		if (y == 'G' || y == 'T') expand = true;
	}

	int realM = M;
	if (expand) {
		M *= 3;
		K *= 2;
	}
	int N2 = (N + 63) / 64;
	vector<vector<uint64_t>> strings(M, vector<uint64_t>(N2));
	vector<bool> iscandidate(N, true);
	vector<int> rc(N);
	vector<vector<int>> mat(N, vector<int>(M));
	int ncand = N;
	for (int i = 0; i < N; ++i) {
		string& str = input[i];
		int co = 0;
		for (int j = 0; j < realM; ++j) {
			int v = (str[j] >> 1) & 3;
			if (expand) {
				int v0 = 0, v1 = 0, v2 = 0;
				if (v == 0) v0 = v1 = v2 = 1;
				else if (v == 1) v0 = 1;
				else if (v == 2) v1 = 1;
				else if (v == 3) v2 = 1;
				int j0 = 3*j+0;
				int j1 = 3*j+1;
				int j2 = 3*j+2;

				strings[j0][i / 64] |= uint64_t(v0) << (i & 63);
				mat[i][j0] = 1 - 2 * v0;
				co += v0;
				strings[j1][i / 64] |= uint64_t(v1) << (i & 63);
				mat[i][j1] = 1 - 2 * v1;
				co += v1;
				strings[j2][i / 64] |= uint64_t(v2) << (i & 63);
				mat[i][j2] = 1 - 2 * v2;
				co += v2;
			} else {
				strings[j][i / 64] |= uint64_t(v) << (i & 63);
				mat[i][j] = 1 - 2 * v;
				co += v;
			}
		}
		rc[i] = co;
	}

	vector<bool> included(N);
	vector<uint64_t> bincluded(N2);
	vector<int> count(M, 0);
	while (ncand > 1) {
		unsigned int nincluded = 0;
		bincluded.assign(N2, 0);
		for (int i = 0; i < N; ++i) {
			included[i] = (rand() >> 14) & 1;
			bincluded[i / 64] |= uint64_t(included[i]) << (i & 63);
			nincluded += included[i] ? 1 : 0;
		}
		for (int j = 0; j < M; ++j) {
			int co = 0;
			for (int i = 0; i < N2; ++i)
				co += __builtin_popcountll(strings[j][i] & bincluded[i]);
			count[j] = co;
		}
		for (int i = 0; i < N; ++i) {
			if (!iscandidate[i]) continue;
			unsigned int sumdif = 0;
			for (int j = 0; j < M; ++j)
				sumdif += count[j] * mat[i][j];
			sumdif += nincluded * rc[i];
			unsigned int expectedsumdif = nincluded * K - (included[i] ? K : 0);
			if (sumdif != expectedsumdif) {
				iscandidate[i] = false;
				--ncand;
			}
		}
	}
	for (int i = 0; i < N; ++i) {
		if (iscandidate[i]) {
			cout << i + 1 << endl;
			return 0;
		}
	}
	cout << "nothing!" << endl;
	return 1;
}

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