Submission #784350

#	Time	Username	Problem	Language	Result	Execution time	Memory
784350		raysh07	Genetics (BOI18_genetics)	C++17	100 / 100	339 ms	36296 KiB

genetics

#include <bits/stdc++.h>
#define pb push_back
#define int int64_t
#define pii pair<int, int>
#define X first
#define Y second
#define all(x) (x).begin(),(x).end()
#define lb lower_bound
#define ub upper_bound
 
using namespace std;
 
const int inf = 1e18;
const int mod = 1e9+7;
const int prime = 7177;
 
void p(auto A){
	for(auto e : A)cout << e << ' ';
	cout << '\n';
}
 
void solve(){
	int n, m, k; cin >> n >> m >> k;
	vector<string>A(n);
	for(int i = 0; i< n; i++)cin >> A[i];
	int base = 1;
	vector<array<int, 4>>cnt(m, {0, 0, 0, 0});
	
	auto f = [](char c){
		if(c=='A')return 0;
		if(c=='C')return 1;
		if(c=='G')return 2;
		return 3;
	};
	
	int ans = 0;
	for(auto S : A){
		ans = (ans + (k*base)%mod)%mod;
		for(int i = 0; i< m; i++){
			for(int j = 0; j< 4; j++)if(f(S[i])!=j)cnt[i][j] = (cnt[i][j] + base) % mod;
		}
		base = base * prime % mod;
	}
	
	base=1;
	for(int i = 0; i< n; i++){
		int cur = 0;
		for(int j = 0; j< m; j++)cur = (cur + cnt[j][f(A[i][j])]) % mod;
		if((cur + (k*base)%mod) % mod == ans){
			cout << i+1;
			return;
		}
		base = base * prime % mod;
	}
	cout << -1;
}
	
 
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int t = 1;
	//cin >> t;
	while(t--)solve();
}
 
 

Compilation message (stderr)

genetics.cpp:17:8: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   17 | void p(auto A){
      |        ^~~~

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