Submission #952670

#	Time	Username	Problem	Language	Result	Execution time	Memory
952670		Ellinor	Genetics (BOI18_genetics)	C++14	100 / 100	1848 ms	36380 KiB

genetics

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens
#pragma GCC optimize("unroll-loops")
#pragma GCC target("bmi,bmi2,lzcnt,popcnt") // bit manipulation
#pragma GCC target("movbe")                 // byte swap
#pragma GCC target("aes,pclmul,rdrnd")      // encryption
#pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2")

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define rep(i, a, b) for (int i = (a); i < int(b); i++)     // in , ex
#define rrep(i, a, b) for (int i = (a)-1; i >= int(b); i--) // ex, in
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

inline void fast()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const ll INF = 100000000000000000; // 1e17
const ll MOD = 1e9 + 7;

//

random_device rd;
mt19937 rng(rd());
template <typename T>
inline T randint(T lo, T hi) { return uniform_int_distribution<T>(lo, hi)(rng); }

#define int ll
#define float double

//

int N, M, K;
vector<string> ns;

vector<bool> na, checked;

vector<pii> score;

vector<array<int, 4>> sum; // A, C, G, T

bool g4 = false;

int32_t main()
{
    fast();

    cin >> N >> M >> K;

    ns.assign(N, "");
    rep(i, 0, N)
    {
        cin >> ns[i];
    }

    //

    sum.assign(M, {0, 0, 0, 0});

    rep(i, 0, N)
    {
        rep(j, 0, M)
        {
            if (ns[i][j] == 'A')
                sum[j][0]++;
            else if (ns[i][j] == 'C')
                sum[j][1]++;
            else if (ns[i][j] == 'G')
            {
                sum[j][2]++;
                g4 = true;
            }
            else
            {
                sum[j][3]++;
                g4 = true;
            }
        }
    }

    na.assign(N, true);

    rep(i, 0, N)
    {
        ll cnt = 0;

        rep(j, 0, M)
        {
            if (ns[i][j] == 'A')
                cnt += (N - sum[j][0]);
            else if (ns[i][j] == 'C')
                cnt += (N - sum[j][1]);
            else if (ns[i][j] == 'G')
                cnt += (N - sum[j][2]);
            else
                cnt += (N - sum[j][3]);
        }

        if (cnt % (N - 1) == 0)
        {
            cnt /= (N - 1);

            if (cnt != K)
                na[i] = false;
        }
        else
            na[i] = false;
    }

    //

    score.assign(N, {0, -1});
    rep(i, 0, N) score[i].second = i;

    if (N > 500 && M > 500 && g4)
    {
        checked.assign(M, false);

        int tmp = 0;

        while (tmp < 10)
        {
            int che = randint(int(0), int(M - 1));

            if (checked[che])
                continue;
            checked[che] = true;
            tmp++;

            char cha;
            if (K < M / 2)
            {
                int m = 0;
                m = max(m, sum[che][0]);
                m = max(m, sum[che][1]);
                m = max(m, sum[che][2]);
                m = max(m, sum[che][3]);

                if (m == sum[che][0])
                    cha = 'A';
                else if (m == sum[che][1])
                    cha = 'C';
                else if (m == sum[che][2])
                    cha = 'G';
                else
                    cha = 'T';
            }
            else
            {
                int m = M;
                if (sum[che][0] != 0)
                    m = min(m, sum[che][0]);
                if (sum[che][1] != 0)
                    m = min(m, sum[che][1]);
                if (sum[che][2] != 0)
                    m = min(m, sum[che][2]);
                if (sum[che][3] != 0)
                    m = min(m, sum[che][3]);

                if (m == sum[che][0])
                    cha = 'A';
                else if (m == sum[che][1])
                    cha = 'C';
                else if (m == sum[che][2])
                    cha = 'G';
                else
                    cha = 'T';
            }

            rep(i, 0, N)
            {
                if (ns[i][che] == cha)
                    score[i].first += 1;
            }
        }

        sort(rall(score));
    }

    //

    rep(_, 0, N)
    {
        int i = score[_].second;

        if (!na[i])
            continue;

        rep(j, 0, N)
        {
            if (j == i)
                continue;

            int cnt = 0;

            rep(k, 0, M)
            {
                if (ns[i][k] != ns[j][k])
                    cnt++;
            }

            if (cnt != K)
            {
                na[i] = false;
                na[j] = false;
                break;
            }
        }

        if (na[i])
        {
            cout << i + 1 << "\n";

            return 0;
        }
    }
}

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