Submission #825418

#	Time	Username	Problem	Language	Result	Execution time	Memory
825418		QwertyPi	Genetics (BOI18_genetics)	C++14	19 / 100	2017 ms	20896 KiB

genetics

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

const int MAXN = 4100 + 11;

bitset<4100> A0[4100], A1[4100];
bitset<4100> B, B0, B1;
int f(char c){
	if(c == 'A') return 0;
	if(c == 'C') return 1;
	if(c == 'G') return 2;
	if(c == 'T') return 3;
}

bool fail[MAXN];

int32_t main(){
	random_device rd;
	mt19937 rng(rd());

	int n, m, k; cin >> n >> m >> k;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			char c; cin >> c;
			int x = f(c);
			A0[i].set(j, x % 2);
			A1[i].set(j, x / 2);
		}
	}

	vector<int> p(n); for(int i = 0; i < n; i++) p[i] = i;
	for(int i = 0; i < n; i++) swap(p[i], p[rng() % (i + 1)]);
	for(int i = 0; i < n; i++){
		if(fail[p[i]]) continue;
		bool ok = true;
		for(int j = 0; j < n; j++){
			if(i == j) continue;
			B0 = A0[p[i]] ^ A0[p[j]];
			B1 = A1[p[i]] ^ A1[p[i]];
			B = B0 | B1;
			if(B.count() != k){
				fail[p[i]] = fail[p[j]] = true;
				ok = false;
				break;
			}
		}
		if(ok){
			cout << p[i] + 1 << endl;
			return 0;
		}
	}
}

Compilation message (stderr)

genetics.cpp: In function 'int32_t main()':
genetics.cpp:41:17: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   41 |    if(B.count() != k){
      |       ~~~~~~~~~~^~~~
genetics.cpp: In function 'int f(char)':
genetics.cpp:13:1: warning: control reaches end of non-void function [-Wreturn-type]
   13 | }
      | ^

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