Submission #522385

#	Time	Username	Problem	Language	Result	Execution time	Memory
522385		LucaDantas	Genetics (BOI18_genetics)	C++17	46 / 100	349 ms	16372 KiB

genetics

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

constexpr int maxn = 1810;

string a[maxn];
bitset<maxn> b[maxn];

int dist(string x, string y) {
	int ans = 0;
	for(int i = 0; i < x.size(); i++)
		ans += x[i] != y[i];
	return ans;
}

int main() {
	int n, m, k; cin >> n >> m >> k;
	string s;
	for(int i = 0; i < n; i++) {
		cin >> s; a[i] = s;
		for(int i = 0; i < m; i++)
			s[i] = (s[i] == 'A') + '0';
		b[i] = bitset<maxn>(s);
	}

	for(int i = 0; i < n; i++) {
		bool ok = 1;
		for(int j = 0; j < n; j++) {
			if(i == j) continue;
			if(max(n, m) > 100) { if((b[i]^b[j]).count() != k) { ok = 0; break; } }
			else if(dist(a[i], a[j]) != k) { ok = 0; break; }
		}
		if(ok) printf("%d\n", i+1);
	}
}

Compilation message (stderr)

genetics.cpp: In function 'int dist(std::string, std::string)':
genetics.cpp:11:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |  for(int i = 0; i < x.size(); i++)
      |                 ~~^~~~~~~~~~
genetics.cpp: In function 'int main()':
genetics.cpp:30:49: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |    if(max(n, m) > 100) { if((b[i]^b[j]).count() != k) { ok = 0; break; } }
      |                             ~~~~~~~~~~~~~~~~~~~~^~~~

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