Submission #1109320

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109320		_rain_	Genetics (BOI18_genetics)	C++14	100 / 100	416 ms	36680 KiB

genetics

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

typedef long long ll;
#define name "main"

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int Rand(int l,int r){
	return uniform_int_distribution<int>(l,r)(rng);
}
const int N=41'00;
const int MOD1=1e9+7;
const int MOD2=998244353;
const int base=2;
string s[N+2];
int n,m,k;
ll cnt[N+2][6][2]={};
ll v[N+2][2]={};
int GetID(char c){	
	if (c=='A') return 0;
	if (c=='T') return 1;
	if (c=='G') return 2;
	if (c=='C') return 3;
}

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n>>m>>k;
	ll hash1=0,hash2=0;
	ll sum1=0,sum2=0;
	for(int i=1;i<=n;++i){
		cin>>s[i];
		hash1=(hash1*base+i)%MOD1;
		hash2=(hash2*base+i)%MOD2;
		v[i][0]=hash1;
		v[i][1]=hash2;
		sum1=(sum1+v[i][0])%MOD1;
		sum2=(sum2+v[i][1])%MOD2;
		for(int j=0;j<m;++j){
			int t=GetID(s[i][j]);
			for(int l=0;l<=3;++l){
				if (t==l) continue;
				cnt[j][l][0]=(cnt[j][l][0]+hash1)%MOD1;
				cnt[j][l][1]=(cnt[j][l][1]+hash2)%MOD2;
			}
		}
	}
	for(int i=1;i<=n;++i){
		ll cur1=0,cur2=0;
		for(int j=0;j<m;++j){
			cur1=(cur1+cnt[j][GetID(s[i][j])][0])%MOD1;
			cur2=(cur2+cnt[j][GetID(s[i][j])][1])%MOD2;
		}
		ll need1=(sum1-v[i][0]+MOD1)%MOD1;
		need1=(need1*k)%MOD1;
		ll need2=(sum2-v[i][1]+MOD2)%MOD2;
		need2=(need2*k)%MOD2;
		if (need1==cur1&&need2==cur2){
			cout<<i<<'\n';
			exit(0);
		}
	}
	exit(0);
}

Compilation message (stderr)

genetics.cpp: In function 'int GetID(char)':
genetics.cpp:24:1: warning: control reaches end of non-void function [-Wreturn-type]
   24 | }
      | ^

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