| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1093500 | CDuong | Genetics (BOI18_genetics) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
#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 (isz(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
}