Submission #594086

#	Time	Username	Problem	Language	Result	Execution time	Memory
594086		Zanite	Genetics (BOI18_genetics)	C++17	0 / 100	280 ms	53492 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	= 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;}

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("%d %d %d", &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[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 <= 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:41:10: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll*' {aka 'long long int*'} [-Wformat=]
   41 |  scanf("%d %d %d", &N, &M, &K);
      |         ~^         ~~
      |          |         |
      |          int*      ll* {aka long long int*}
      |         %lld
genetics.cpp:41:13: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'll*' {aka 'long long int*'} [-Wformat=]
   41 |  scanf("%d %d %d", &N, &M, &K);
      |            ~^          ~~
      |             |          |
      |             int*       ll* {aka long long int*}
      |            %lld
genetics.cpp:41:16: warning: format '%d' expects argument of type 'int*', but argument 4 has type 'll*' {aka 'long long int*'} [-Wformat=]
   41 |  scanf("%d %d %d", &N, &M, &K);
      |               ~^           ~~
      |                |           |
      |                int*        ll* {aka long long int*}
      |               %lld
genetics.cpp:47:13: warning: array subscript has type 'char' [-Wchar-subscripts]
   47 |    DNA[corr[buf]][i][j] = 1;
      |             ^~~
genetics.cpp:72:13: warning: format '%d' expects argument of type 'int', but argument 2 has type 'll' {aka 'long long int'} [-Wformat=]
   72 |    printf("%d\n", comp);
      |            ~^     ~~~~
      |             |     |
      |             int   ll {aka long long int}
      |            %lld
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