Submission #594089

#	Time	Username	Problem	Language	Result	Execution time	Memory
594089		Zanite	Genetics (BOI18_genetics)	C++17	100 / 100	1946 ms	543256 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 ll maxN	= 4101;

const ll mod	= 1'690'758'499;
const ll maxW	= 1'000'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;}

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

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

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

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

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

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

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

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

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

Compilation message (stderr)

genetics.cpp: In function 'int main()':
genetics.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  scanf("%lld %lld %lld", &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: 27 / 27
• Subtask 2: 19 / 19
• Subtask 3: 28 / 28
• Subtask 4: 26 / 26