Submission #861725

#	Time	Username	Problem	Language	Result	Execution time	Memory
861725		serifefedartar	Genetics (BOI18_genetics)	C++17	100 / 100	258 ms	33632 KiB

genetics

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9+9;
const ll LOGN = 20; 
const ll MAXN = 4100 + 100;

const ll P = 31;
ll cnt[MAXN][4];
ll need = 0;
string dna[MAXN];

int main() {
	fast
	int N, M, K;
	cin >> N >> M >> K;

	ll now = 1;
	for (int i = 1; i <= N; i++) {
		now = (now * P) % MOD;
		need = (need + (now * K % MOD)) % MOD;
		cin >> dna[i];
		dna[i] = "#" + dna[i];
		for (int j = 1; j <= M; j++) {
			if (dna[i][j] == 'A')
				cnt[j][0] = (cnt[j][0] + now) % MOD;
			else if (dna[i][j] == 'T')
				cnt[j][1] = (cnt[j][1] + now) % MOD;
			else if (dna[i][j] == 'G')
				cnt[j][2] = (cnt[j][2] + now) % MOD;
			else if (dna[i][j] == 'C')
				cnt[j][3] = (cnt[j][3] + now) % MOD;
		}
	}

	now = 1;
	for (int i = 1; i <= N; i++) {
		now = (now * P) % MOD;
		ll need_now = need - (now * K % MOD);
		while (need_now < 0)
			need_now += MOD;

		ll calc = 0;
		for (int j = 1; j <= M; j++) {
			if (dna[i][j] == 'A')
				calc = (calc + (cnt[j][1] + cnt[j][2] + cnt[j][3])) % MOD;
			else if (dna[i][j] == 'T')
				calc = (calc + (cnt[j][0] + cnt[j][2] + cnt[j][3])) % MOD;
			else if (dna[i][j] == 'G')
				calc = (calc + (cnt[j][0] + cnt[j][1] + cnt[j][3])) % MOD;
			else if (dna[i][j] == 'C')
				calc = (calc + (cnt[j][0] + cnt[j][1] + cnt[j][2])) % MOD;
		}

		if (calc == need_now) {
			cout << i << "\n";
			return 0;
		}
	}
}

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