Submission #566328

#	Time	Username	Problem	Language	Result	Execution time	Memory
566328		hohohaha	Genetics (BOI18_genetics)	C++14	100 / 100	1045 ms	22112 KiB

genetics

#include<bits/stdc++.h>
using namespace std;
#define fori(i, l, r) for(int i = (int) (l); i <= (int) (r); i++) 
#define ford(i, r, l) for(int i = (int) (r); i >= (int) (l); i--) 
#define ii pair<int, int> 
#define fi first
#define se second
#define vi vector<int> 
#define eb emplace_back
#define sp ' '
#define endl '\n'
#define int long long
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count()); 

const int maxn = 4105, mod = 1e9 + 9; 

int n, m, k; 
string s[maxn]; 
int pw[maxn]; 
int Hash[maxn][4]; 
int sum[maxn]; 
int cv(int c) { 
	return c == 'A'? 0: c == 'C'? 1: c == 'G'? 2: 3; 
}
signed main() { 
	ios_base::sync_with_stdio(0); 
	cin.tie(0); 
	cout.tie(0);

	cin >> n >> m >> k; 
	pw[0] = 1; 
	fori(i, 1, maxn - 1) pw[i] = pw[i - 1] * (k + 1) % mod; 
	fori(i, 1, n ) { 
		cin >> s[i]; 
	}
	fori(i, 0, m - 1) { 
		fori(j, 1, n) { 
			(Hash[i][cv(s[j][i])] += pw[j]) %= mod; 
		}
		fori(j, 1, n) { 
			fori(c, 0, 3) {
				if(c != cv(s[j][i])) (sum[j] += Hash[i][c]) %= mod; 
			}
		}
	}
	int des = 0; fori(i, 1, n) (des += k * pw[i]) %= mod; 
	fori(i, 1, n) { 
		if((sum[i] + k * pw[i]) % mod == des) { 
			cout << i << endl; 
		}
	}
}

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