Submission #1105590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105590		nrg_studio	Genetics (BOI18_genetics)	C++17	100 / 100	701 ms	33820 KiB

genetics

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

#define ll long long
#define pb push_back
#define pii pair<ll,ll>
#define f first
#define s second
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)

int mod = 1e9+7;
ll rng() {
	static mt19937 gen(
	    chrono::steady_clock::now().time_since_epoch().count());
	return uniform_int_distribution<long long>(0,INT32_MAX)(gen);
}

ll mul(ll a, ll b) {return a*b%mod;}
ll add(ll a, ll b) {return (a+b)%mod;}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	
	int n, m, k; cin >> n >> m >> k;
	vector<ll> p(n);
	F0R(i,n) {p[i] = rng();}

	vector<vector<ll>> hsh(m,vector<ll>(4));
	char c[4] = {'A','C','T','G'};
	vector<vector<char>> gen(n,vector<char>(m));
	F0R(i,n) {
		F0R(j,m) {cin >> gen[i][j];}
	}
	F0R(pos,m) {
		F0R(ch,4) {
			ll h = 0;
			F0R(cow,n) {
				if (gen[cow][pos]==c[ch]) {h = add(h,p[cow]);}
			} hsh[pos][ch] = h;
		}
	}
	F0R(cow,n) {
		ll target = 0;
		F0R(j,n) {
			if (cow!=j) {target = add(target,p[j]);}
		} target = mul(target,k);
		ll h = 0;

		F0R(pos,m) {
			F0R(ch,4) {
				if (c[ch]!=gen[cow][pos]) {h = add(h,hsh[pos][ch]);}
			}
		} 
		if (h==target) {cout << cow+1 << '\n'; break;}
	}
}

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