Submission #1093642

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093642		vjudge1	Genetics (BOI18_genetics)	C++17	100 / 100	169 ms	36316 KiB

genetics

#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2")
#include<bits/stdc++.h>
#define all(x) (x).begin() , (x).end()
#define pll pair<long long, long long>
#define fi first 
#define se second 
#define bit(i,j) ((j >> i) & 1) 
#define lowbit(x) (x & (-x))
#define sigma main
using namespace std;

const long long inf = 1e9+1; 
const int mod = 998244353; 
const int MAXN = 5e4+100;

#define int long long

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

int Rand(int l , int r){
	return uniform_int_distribution<int>(l, r)(rd);
}

int cnt[256];
int32_t sigma(){
  	//freopen("COLOREDBALLS.inp", "r", stdin);
	//freopen("COLOREDBALLS.out", "w", stdout);
	ios_base::sync_with_stdio(0); cin.tie(0);

	int n , m , k; cin >> n >> m >> k;
	vector<string> s(n+1);
	for(int i = 1 ; i <= n ; i++) cin >> s[i];

	vector<int> v(n+1);
	int tot = 0;
	for(int i = 1 ; i <= n ; i++) v[i] = Rand(1 , 1e12) , tot += v[i];

	vector<int> sum(n + 1);

	for(int i = 0 ; i < m ; i++){
		cnt['A'] = 0 ; cnt['C'] = 0 ; cnt['G'] = 0 ; cnt['T'] = 0;
		for(int j = 1 ; j <= n ; j++) cnt[s[j][i]] += v[j];
		for(int j = 1 ; j <= n ; j++){
			sum[j] += tot - cnt[s[j][i]];
		}
	}

	for(int i = 1 ; i <= n ; i++){
		if(sum[i] == (tot - v[i]) * k){
			cout << i << "\n"; return 0;
		}
	}

	return 0;
}

Compilation message (stderr)

genetics.cpp: In function 'int32_t main()':
genetics.cpp:43:44: warning: array subscript has type 'char' [-Wchar-subscripts]
   43 |   for(int j = 1 ; j <= n ; j++) cnt[s[j][i]] += v[j];
      |                                            ^
genetics.cpp:45:31: warning: array subscript has type 'char' [-Wchar-subscripts]
   45 |    sum[j] += tot - cnt[s[j][i]];
      |                               ^

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