Submission #1093521

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093521		CDuong	Genetics (BOI18_genetics)	C++17	100 / 100	198 ms	36544 KiB

genetics

/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/

#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define isz(x) (int)x.size()
using namespace std;

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rngll(chrono::high_resolution_clock::now().time_since_epoch().count());
using randint_t = uniform_int_distribution<int>;
using randll_t = uniform_int_distribution<long long>;
using randd_t = uniform_real_distribution<double>;
// return x with probability p, y with probability 1-p
template<class T>
T pick(T x, T y, double p = 0.5){
    assert(-0.0001 <= p && p <= 1.0001);
    return randd_t(0, 1)(rng) <= p ? x : y;
}
array<int, 2> gen_range(int n, bool allow_empty_range = false){
    if(allow_empty_range){
        int l = rng() % (n + 1), r = rng() % (n + 1);
        if(l > r) swap(l, r);
        return {l, r};
    }
    else{
        int l = rng() % n, r = rng() % n;
        if(l > r) swap(l, r);
        return {l, r + 1};
    }
}
template<class T>
vector<T> sample_array(int n, T low, T high, bool distinct = false){
    assert(low < high && (!distinct || high - low >= n));
    set<T> used;
    vector<T> array(n);
    for(auto i = 0; i < n; ++ i){
        T x = randll_t(low, high - 1)(rng);
        if(distinct){
            if(used.count(x)){
                -- i;
                continue;
            }
            used.insert(x);
        }
        array[i] = x;
    }
    return array;
}

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    
    vector<string> a(n);
    for (auto &val : a) cin >> val;

    vector<int> dec(256);
    dec['A'] = 0, dec['C'] = 1, dec['G'] = 2, dec['T'] = 3;

    vector<int> hsh(n);
    vector sumhsh(m, vector(4, 0ll));

    i64 allhsh = 0;
    for (int i = 0; i < n; ++i) {
        hsh[i] = rng();
        for (int j = 0; j < m; ++j) {
            int ch = dec[a[i][j]];
            sumhsh[j][ch] += hsh[i];
        }
        allhsh += hsh[i];
    }

    for (int i = 0; i < n; ++i) {
        i64 cur = 0;
        for (int j = 0; j < m; ++j) {
            for (int ch = 0; ch < 4; ++ch) if (ch != dec[a[i][j]]) {
                cur += sumhsh[j][ch];
            }
        }
        if (cur == (allhsh - hsh[i]) * k) {
            cout << i + 1 << endl;
            return;
        }
    }
}

signed main() {

#ifndef CDuongg
    if (fopen(taskname".inp", "r"))
        assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
    freopen("bai3.inp", "r", stdin);
    freopen("bai3.out", "w", stdout);
    auto start = chrono::high_resolution_clock::now();
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1; //cin >> t;
    while(t--) solve();

#ifdef CDuongg
   auto end = chrono::high_resolution_clock::now();
   cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
   cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif

}

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