Submission #1131456

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131456		Alihan_8	Genetics (BOI18_genetics)	C++20	100 / 100	346 ms	17724 KiB

genetics

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define size(x) (int)(x).size()
#define int long long

typedef pair <int,int> pii;

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
#define rnd(l, r) uniform_int_distribution <int> (l, r)(rng)

const int Mod = 1e14 + 7;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
	int n, m, k; cin >> n >> m >> k;
	
	vector <ar<int,4>> cnt(m);
	vector <int> w(n);
	vector <string> t(n);
	
	for ( int i = 0; i < n; i++ ) w[i] = rnd(0, Mod - 1);
	
	auto id = [&](char x){ return x == 'A' ? 0 : x == 'G' ? 1 : x == 'C' ? 2 : 3; };
	
	for ( int i = 0; i < n; i++ ){
		string s; cin >> s;
		
		t[i] = s;
		
		for ( int j = 0; j < m; j++ ){
			int x = id(s[j]);
			
			cnt[j][x] += w[i];
			cnt[j][x] %= Mod;
		}
	}
	
	int tot = 0;
	
	for ( auto &x: w ) tot = (tot + x) % Mod;
	
	for ( int i = 0; i < n; i++ ){
		int cur = (tot - w[i] + Mod) % Mod, f = 0;
		
		cur = cur * k % Mod;
		
		for ( int j = 0; j < m; j++ ){	
			for ( int k = 0; k < 4; k++ ){
				if ( k != id(t[i][j]) ){
					f = (f + cnt[j][k]) % Mod;
				} 
			}
		}
			
		if ( f == cur ) return cout << i + 1 << '\n', 0;
	}
	
	assert(false);
    	
    cout << '\n';
}

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