Submission #952638

#	Time	Username	Problem	Language	Result	Execution time	Memory
952638		Ellinor	Genetics (BOI18_genetics)	C++14	74 / 100	2086 ms	36536 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()

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;

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

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]++;
            else
                sum[j][3]++;
        }
    }

    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;
    }

    //

    rep(i, 0, N)
    {
        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: 0 / 26