Submission #594068

#	Time	Username	Problem	Language	Result	Execution time	Memory
594068		Zanite	Genetics (BOI18_genetics)	C++17	46 / 100	2017 ms	5916 KiB

genetics

// I am now here, but I have yet to prove that I am worthy of my place here.

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using si	= short int;

const si maxN		= 4101;

si N, M, K;
bitset<maxN> DNA[4][maxN];
bitset<maxN> tmp;
char corr[256];
char buf;

int main() {
	corr[(int)'A'] = 0;
	corr[(int)'C'] = 1;
	corr[(int)'G'] = 2;
	corr[(int)'T'] = 3;

	scanf("%hi %hi %hi", &N, &M, &K);
	K <<= 1;

	for (si i = 1; i <= N; i++) {
		for (si j = 0; j < M; j++) {
			scanf(" %c", &buf);
			DNA[corr[buf]][i][j] = 1;
		}
	}

	vector<si> order(N);
	iota(order.begin(), order.end(), 1);
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	shuffle(order.begin(), order.end(), rng);

	for (si comp = 0; comp < N; comp++) {
		si C = order[comp];
		bool valid = 1;
		for (si other = 0; other < N; other++) {
			si O = order[other];
			if (C == O) continue;
			int d = 0;
			for (int i = 0; i < 4; i++) {
				d += (DNA[i][C] ^ DNA[i][O]).count();
			}
			if (d != K) {
				valid = 0;
				break;
			}
		}

		if (valid) {
			printf("%d\n", C);
			return 0;
		}
	}
}

Compilation message (stderr)

genetics.cpp: In function 'int main()':
genetics.cpp:32:13: warning: array subscript has type 'char' [-Wchar-subscripts]
   32 |    DNA[corr[buf]][i][j] = 1;
      |             ^~~
genetics.cpp:32:16: warning: array subscript has type 'char' [-Wchar-subscripts]
   32 |    DNA[corr[buf]][i][j] = 1;
      |        ~~~~~~~~^
genetics.cpp:26:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |  scanf("%hi %hi %hi", &N, &M, &K);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
genetics.cpp:31:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |    scanf(" %c", &buf);
      |    ~~~~~^~~~~~~~~~~~~

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