Submission #1093501

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093501		CDuong	Genetics (BOI18_genetics)	C++17	27 / 100	2035 ms	3928 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;

    const int tested = 10;

    auto count_diff = [&](int x, int y) -> int {
        int res = 0;
        for (int i = 0; i < m; ++i) {
            res += a[x][i] != a[y][i];
        }
        return res;
    };
    
    vector<int> vis(n);
    while (accumulate(all(vis), 0) < n - 1) {
        for (int i = 0; i < n; ++i) if (not vis[i]) {
            for (int _ = 0; _ < tested; ++_) {
                auto idx = i;
                while (idx == i) {
                    idx = randll_t(0, n - 1)(rng);
                }
                if (count_diff(i, idx) != k) {
                    vis[i] = vis[idx] = true;
                    break;
                }
            }
        }
    }
    
    assert(accumulate(all(vis), 0) == n - 1);
    for (int i = 0; i < n; ++i) if (not vis[i]) {
        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: 0 / 19
• Subtask 3: 0 / 28
• Subtask 4: 0 / 26