Submission #896077

#	Time	Username	Problem	Language	Result	Execution time	Memory
896077		nifeshe	Genetics (BOI18_genetics)	C++17	100 / 100	1256 ms	48044 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;
    map<char, int> go;
    go['A'] = 'A'; go['C'] = 'B'; go['G'] = 'C'; go['T'] = 'D';
    vector<string> a(n);
    for(auto &i : a) {
        cin >> i;
        for(auto &j : i) j = go[j] - 'A';
    }
    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) continue;
        int ok = 1;
        for(int x = 0; x < BUBEN; x++) {
            if(cnt[x] == 0 || idx[i] == x) continue;
            need = cnt[x] * k;
            for(int j = 0; j < m && need >= 0; j++) {
                need -= have[x][j][a[i][j]];
            }
            if(need != 0) {
                ok = 0;
                break;
            }
        }
        if(ok) {
            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);
}

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: 19 / 19
• Subtask 3: 28 / 28
• Subtask 4: 26 / 26