Submission #877813

#	Time	Username	Problem	Language	Result	Execution time	Memory
877813		phoenix0423	Genetics (BOI18_genetics)	C++17	100 / 100	453 ms	36528 KiB

genetics

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
// #pragma GCC optimize("Ofast")
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 0, n + 1)
#define pb push_back
#define pf push_front
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
#define ckmin(a, b) a = min(a, b)
#define ckmax(a, b) a = max(a, b)
const int N = 1e9 + 7;
const int INF = 1e9 + 7;
const int maxn = 5000;
ll have[maxn][4];
map<char, int> mp{{'A', 0}, {'T', 1}, {'C', 2}, {'G', 3}};

int main(void){
	fastio;
	int n, m, k;
	cin>>n>>m>>k;
	vector<string> s(n);
	for(int i = 0; i < n; i++) cin>>s[i];
	random_device rd;
	mt19937 gen;
	uniform_int_distribution<> rng(0, INF);
	vector<int> w(n);
	ll ttlw = 0;
	for(int i = 0; i < n; i++) w[i] = rng(gen), ttlw += w[i];
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++) have[j][mp[s[i][j]]] += w[i];
	}
	for(int i = 0; i < n; i++){
		ll dif = 0;
		for(int j = 0; j < m; j++){
			dif += ttlw - have[j][mp[s[i][j]]];
		}
		if(dif == (ttlw - w[i]) * k){
			cout<<i + 1<<"\n";
			return 0;
		}
	}
}

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