Submission #1194835

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194835		_rain_	Genetics (BOI18_genetics)	C++20	100 / 100	356 ms	19956 KiB

genetics

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

const int MOD1=1e9+9;
const int base = 2;
const int MOD2=998244353;
const int N=(int)4100;
string s[N+2];
int cnt[N+2][4][2]={},val[N+2][2];
int n,m,k;

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

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0)  ;
//	freopen("main.inp","r",stdin);
	
	cin>>n>>m>>k;
	int sum1=0,sum2=0,hash1=0,hash2=0;
	for(int i=1;i<=n;++i){
		cin>>s[i];
		hash1=((LL)hash1*base+i)%MOD1;
		hash2=((LL)hash2*base+i)%MOD2;
		val[i][0]=hash1;
		val[i][1]=hash2;
		sum1=((LL)sum1+val[i][0])%MOD1;
		sum2=((LL)sum2+val[i][1])%MOD2;
		for(int j=0;j<m;++j){
			for(int t=0;t<4;++t){
				if (t==tt(s[i][j])) continue;
				cnt[j][t][0]=((LL)cnt[j][t][0]+val[i][0])%MOD1;
				cnt[j][t][1]=((LL)cnt[j][t][1]+val[i][1])%MOD2;
			}
		}
	}
	
	for(int i=1;i<=n;++i){
		int tmp1=sum1,tmp2=sum2;
		tmp1=((LL)tmp1-val[i][0]+MOD1)%MOD1,tmp2=((LL)tmp2-val[i][1]+MOD2)%MOD2;
		int cur1=0,cur2=0;
		for(int j=0;j<m;++j){
			cur1=((LL)cur1+cnt[j][tt(s[i][j])][0])%MOD1;
			cur2=((LL)cur2+cnt[j][tt(s[i][j])][1])%MOD2;
		}
		tmp1=((LL)tmp1*k)%MOD1;
		tmp2=((LL)tmp2*k)%MOD2;
		if (tmp1==cur1 && tmp2==cur2){
			cout<<i<<'\n';
			return 0;
		}
	}
	cout<<-1;
	return 0;
}

Compilation message (stderr)

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

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