Submission #896069

#	Time	Username	Problem	Language	Result	Execution time	Memory
896069		nifeshe	Genetics (BOI18_genetics)	C++17	27 / 100	26 ms	10588 KiB

genetics

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC target ("avx2")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")

#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int) (x).size())
#define pb push_back
#define mp make_pair
#define int long long

using namespace std;
using namespace __gnu_pbds;

template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T> inline bool umin(T &a, const T &b) { if(a > b) { a = b; return 1; } return 0; }
template <typename T> inline bool umax(T &a, const T &b) { if(a < b) { a = b; return 1; } return 0; }

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll mod = 998244353;
const ll base = 1e6 + 9;
const ll inf = 1e18;
const int MAX = 3e5 + 42;
const int LG = 20;

random_device rd;
mt19937 gen(rd());
uniform_int_distribution<ll> dis(1, inf);

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<string> a(n);
    for(auto &i : a) {
        cin >> i;
        for(auto &j : i) j -= 'A';
    }
    if(n * n * m <= 1e7) {
        for(int i = 0; i < n; i++) {
            bool ok = 1;
            for(int j = 0; j < n; j++) {
                if(j == i) continue;
                int cnt = 0;
                for(int p = 0; p < m && cnt <= k; p++) {
                    cnt += a[i][p] != a[j][p];
                }
                if(cnt != k) {
                    ok = 0;
                    break;
                }
            }
            if(ok) {
                cout << i + 1 << '\n';
                return;
            }
        }
        assert(0);
    }
    const int BUBEN = 40;
    vector<vector<vector<int>>> have(BUBEN, vector<vector<int>>(m, vector<int>(4)));
    vector<int> cnt(BUBEN);
    vector<int> idx(n);
    for(int i = 0; i < n; i++) {
        idx[i] = dis(gen) % BUBEN;
        cnt[idx[i]]++;
        for(int j = 0; j < m; j++) {
            for(int c = 0; c < 4; c++) {
                have[idx[i]][j][c]++;
            }
        }
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            have[idx[i]][j][a[i][j]]--;
        }
    }
    vector<int> p(n); iota(all(p), 0); shuffle(all(p), gen);
    for(auto i : p) {
        int need = (cnt[idx[i]] - 1) * k;
        for(int j = 0; j < m && need >= 0; j++) {
            need -= have[idx[i]][j][a[i][j]];
        }
        if(need == 0) {
            cout << i + 1 << '\n';
            return;
        }
    }
    assert(0);
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int ttt = 1;
//    cin >> ttt;
    while(ttt--) {
        solve();
    }
}

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