Submission #243738

#	Time	Username	Problem	Language	Result	Execution time	Memory
243738		AMO5	Genetics (BOI18_genetics)	C++17	100 / 100	318 ms	26104 KiB

genetics

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define eb emplace_back
#define mt make_tuple
#define all(x) (x).begin(), (x).end() 
#define MOD 1000000007

typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;

const ll INF=LLONG_MAX;
const int mxn=4200;
ll dp[mxn][4];
ll pw[mxn];
string s[mxn];

void mul(ll &a, ll b){
	a%=MOD; b%=MOD; a*=b; a%=MOD;
}

void add(ll &a, ll b){
	a%=MOD; b%=MOD; a+=b; a%=MOD;
}

int conv(char c){
	if(c=='A')return 0;
	if(c=='C')return 1;
	if(c=='G')return 2;
	return 3;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
	int n,m,k;
	cin >> n >> m >> k;
	pw[0]=1ll;
	ll allpw = 0ll, allk = 0ll;
	for(int i=1; i<=n; i++){
		cin >> s[i];		
		pw[i] = pw[i-1]*3ll%MOD;
		add(allpw,pw[i]);
		add(allk,(k*pw[i])%MOD);
		for(int j=0; j<m; j++){
			int ch = conv(s[i][j]);
			add(dp[j][ch],pw[i]);
		}
	}
	for(int i=1; i<=n; i++){
		ll cur = 0ll;
		for(int j=0; j<m; j++){
			int ch = conv(s[i][j]);
			add(cur,(allpw - dp[j][ch]+MOD)%MOD);
		}
		add(cur,k*pw[i]%MOD);
		if(allk==cur){
			cout << i << endl;
			return 0;
		}
	}
}
	
// READ & UNDERSTAND
// ll, int overflow, array bounds, memset(0)
// special cases (n=1?), n+1 (1-index)
// do smth instead of nothing & stay organized
// WRITE STUFF DOWN

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