Submission #594085

#	Time	Username	Problem	Language	Result	Execution time	Memory
594085		Zanite	Genetics (BOI18_genetics)	C++17	0 / 100	296 ms	33080 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 ll	= long long;

const int maxN	= 4101;

const ll mod	= 1'690'758'499;
const ll maxW	= 420'000;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline ll getRand(ll l, ll r) {
	return uniform_int_distribution<ll>(l, r)(rng);
}

inline void maddto(ll &x, ll y) {x += y; if (x > mod) x -= mod;}

inline ll msub(ll x, ll y) {x -= y; if (x < 0) x += mod; return x;}
inline ll mmul(ll x, ll y) {x *= y; x %= mod; return x;}

int N, M, K;
int DNA[4][maxN][maxN];
int corr[256];
char buf;

ll w[maxN], sumW;
ll columnSum[4][maxN];

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

	scanf("%d %d %d", &N, &M, &K);
	K = M - K;

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

		w[i] = getRand(1, maxW);
		maddto(sumW, w[i]);
	}

	for (int j = 1; j <= M; j++) {
		for (int d = 0; d < 4; d++) {
			for (int i = 1; i <= N; i++) {
				maddto(columnSum[d][j], w[i] * DNA[d][i][j]);
			}
		}
	}

	for (int comp = 1; comp <= N; comp++) {
		ll target = mmul(K, msub(sumW, w[comp]));
		ll total = 0;
		for (int d = 0; d < 4; d++) {
			for (int col = 1; col <= N; col++) {
				maddto(total, mmul(DNA[d][comp][col], msub(columnSum[d][col], mmul(w[comp], DNA[d][comp][col]))));
			}
		}

		if (target == total) {
			printf("%d\n", comp);
			return 0;
		}
	}
}

Compilation message (stderr)

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

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