Submission #528619

#	Time	Username	Problem	Language	Result	Execution time	Memory
528619		LucaDantas	Genetics (BOI18_genetics)	C++17	47 / 100	220 ms	214672 KiB

genetics

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

using ull = long long;

mt19937 rng(random_device{}());

constexpr int maxn = 4110;

int a[maxn][maxn], m;
ull w[maxn], modified[maxn][maxn], tudo[maxn], soma_pesos; // sum of the row

ull dot(int x[], ull y[]) {
	ull ans = 0;
	for(int i = 0; i < m; i++)
		ans += x[i] * y[i];
	return ans;
}

int main() {
	int n, k; scanf("%d %d %d", &n, &m, &k);
	k = m - 2*k; // k vira k'
	for(int i = 0; i < n; i++) {
		char s[maxn]; scanf(" %s", s);
		for(int j = 0; j < m; j++) {
			a[i][j] = s[j] == 'A' ? 1 : -1; // estou codando para o caso onde só existem as letras A e C
		}
	}

	for(int i = 0; i < n; i++) // defino o peso de cada coluna
		w[i] = (ull) rng(), soma_pesos += w[i];

	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++)
			modified[i][j] = (ull) a[i][j] * w[i], tudo[j] += modified[i][j];
	}

	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++)
			tudo[j] -= modified[i][j];
		
		bool ans = dot(a[i], tudo) == (soma_pesos - w[i]) * k;

		for(int j = 0; j < m; j++)
			tudo[j] += modified[i][j];

		if(ans) return printf("%d\n", i+1), 0;
	}
}

Compilation message (stderr)

genetics.cpp: In function 'int main()':
genetics.cpp:21:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |  int n, k; scanf("%d %d %d", &n, &m, &k);
      |            ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
genetics.cpp:24:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |   char s[maxn]; scanf(" %s", s);
      |                 ~~~~~^~~~~~~~~~

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