Submission #846586

#	Time	Username	Problem	Language	Result	Execution time	Memory
846586		vjudge1	Genetics (BOI18_genetics)	C++17	100 / 100	508 ms	65348 KiB

genetics

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

const int N = 1e6 + 5;
const int mod = 1e9 + 7;
const int base = 31;

char c[4] = {'A' , 'C' , 'G' , 'T'};

string s[N];

main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n , m , k; cin >> n >> m >> k;
	vector <long long> pow(n + 1); vector <vector <int>> ans(m + 1 , vector <int> (4));
	for(int i = 1; i <= n; i++) cin >> s[i] , s[i] = ' ' + s[i];
	pow[0] = 1;
	for(int i = 1; i <= n; i++) pow[i] = (pow[i -1] * base) % mod;
	for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) for(int d = 0; d < 4; d++) if(s[i][j] != c[d]) ans[j][d] = (ans[j][d] + pow[i]) % mod;
	for(int i = 1; i <= n; i++) {
		int sum = 0; int tmp = 0;
		for(int j = 1; j <= n; j++) if(i != j) sum = (sum + pow[j] * k) % mod;
  		for(int j = 1; j <= m; j++) for(int d = 0; d < 4; d++) if(s[i][j] == c[d]) tmp = (tmp + ans[j][d]) % mod;			
		if(tmp == sum) cout << i;
	}
	return 0x0;
}

Compilation message (stderr)

genetics.cpp:12:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   12 | main() {
      | ^~~~

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