Submission #790629

#	Time	Username	Problem	Language	Result	Execution time	Memory
790629		AngusRitossa	Genetics (BOI18_genetics)	C++14	46 / 100	2065 ms	44972 KiB

genetics

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, k, m;
char dna[4110][4110];
ll thing[4110][70];
bool isbad[4110];
bool isgood[4110][4110];
int pop_count(ll x)
{
	int ans = 0;
	while (x & -x)
	{
		ans++;
		x -= (x & -x);
	}
	return ans;
}
int main()
{
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			scanf(" %c", &dna[i][j]);
			if (dna[i][j] == 'A')
			{
				ll mod = j%60;
				ll div = j/60;
				thing[i][div] |= (1ll << mod);
			}
		}
	}
	int div = m/60;
	div++;
	if (n+m > 200)
	{
	for (int i = 0; i < n; i++)
	{
		if (isbad[i]) continue;
		bool works = 1;
		for (int j = 0; j < n; j++)
		{
			if (i == j || isgood[i][j]) continue;
			ll diff = 0;
			for (int l = 0; l <= div; l++)
			{
				diff += pop_count(thing[i][l] ^ thing[j][l]);
			}
			if (diff != k) 
			{
				isbad[j] = 1;
				works = 0;
				break;
			}
			isgood[j][i] = 1;
		}
		if (works)
		{
			printf("%d\n", i+1);
			return 0;
		}
	}
	}
	else
	{
		for (int i = 0; i < n; i++)
	{
		bool works = 1;
		for (int j = 0; j < n; j++)
		{
			if (i == j) continue;
			int diff = 0;
			for (int l = 0; l < m; l++)
			{
				if (dna[i][l] != dna[j][l]) diff++;
			}
			if (diff != k) 
			{
				works = 0;
				break;
			}
		}
		if (works)
		{
			printf("%d\n", i+1);
			return 0;
		}
	}
	}
}

Compilation message (stderr)

genetics.cpp: In function 'int main()':
genetics.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |  scanf("%d%d%d", &n, &m, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
genetics.cpp:26:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |    scanf(" %c", &dna[i][j]);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~

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