Submission #378257

#	Time	Username	Problem	Language	Result	Execution time	Memory
378257		Nima_Naderi	Genetics (BOI18_genetics)	C++14	100 / 100	543 ms	36552 KiB

genetics

///In the name of GOD
//#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MXN = 4100 + 10;
const ll Mab = 4783;
const ll Mod = 1e9 + 87;
ll n, m, k;
ll hsh[MXN][4], pw[MXN], one[MXN];
string S[MXN];
void mkay(ll& x){
	if(x >= Mod) x -= Mod;
	if(x < 0) x += Mod;
}
ll MAP(char c){
	switch(c){
		case 'A' : return 0;
		case 'T' : return 1;
		case 'C' : return 2;
		case 'G' : return 3;
	}
	assert(0);
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
	pw[0] = one[0] = 1;
	for(int i = 1; i < MXN; i ++){
		pw[i] = pw[i - 1] * Mab % Mod;
		one[i] = (one[i - 1] + pw[i]) % Mod;
	}
	cin >> n >> m >> k;
	for(int i = 0; i < n; i ++) cin >> S[i];
	for(int i = 0; i < n; i ++){
		for(int j = 0; j < m; j ++){
			ll ch = MAP(S[i][j]);
			hsh[j][ch] += pw[i];
			mkay(hsh[j][ch]);
		}
	}
	for(int j = 0; j < m; j ++) for(int c = 0; c < 4; c ++){
		hsh[j][c] = one[n - 1] - hsh[j][c];
		mkay(hsh[j][c]);
	}
	ll exp = one[n - 1] * k % Mod;
	for(int i = 0; i < n; i ++){
		ll diff = 0;
		for(int j = 0; j < m; j ++){
			ll ch = MAP(S[i][j]);
			diff += hsh[j][ch];
			mkay(diff);
		}
		exp -= pw[i] * k % Mod, mkay(exp);
		if(diff == exp) return cout << i + 1 << '\n', 0;
		exp += pw[i] * k % Mod, mkay(exp);
	}
	cout << "wtmoo" << '\n';
	return 0;
}
/*!
    HE'S AN INSTIGATOR,
    ENEMY ELIMINATOR,
    AND WHEN HE KNOCKS YOU BETTER
    YOU BETTER LET HIM IN.
*/
//! N.N

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