Submission #1090397

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090397		andrei_iorgulescu	Genetics (BOI18_genetics)	C++14	27 / 100	2031 ms	11316 KiB

genetics

#include <bits/stdc++.h>

using namespace std;

mt19937 rng(8962);

int n, m, k;
char a[4105][4105];
bitset<8205> bs[4105];
bitset<4105> f0[4105], f1[4105], f2[4105], f3[4105];

int ff(int x, int y)
{
    int xx = (bs[x] ^ bs[y]).count() - (f0[x] & f1[y]).count() - (f1[x] & f0[y]).count() - (f2[x] & f3[y]).count() - (f3[x] & f2[y]).count();
    return xx;
}

bool mna(int x, int y)
{
    int xx = ff(x, y);
    if (xx == k)
        return true;
    return false;
}

bool candi[4105];
int df[4105];

void muta(int x, int y)
{
    vector<int> dife;
    for (int i = 1; i <= m; i++)
    {
        if (a[x][i] != a[y][i])
            dife.push_back(i);
    }
    for (int i = 1; i <= n; i++)
    {
        for (auto it : dife)
        {
            if (a[i][it] != a[x][it])
                df[i]--;
            if (a[i][it] != a[y][it])
                df[i]++;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            {
                if (a[i][j] == 'A')
                    bs[i][2 * j - 1] = bs[i][2 * j] = 0;
                else if (a[i][j] == 'C')
                    bs[i][2 * j] = 1;
                else if (a[i][j] == 'G')
                    bs[i][2 * j - 1] = 1;
                else
                    bs[i][2 * j - 1] = bs[i][2 * j] = 1;
                if (a[i][j] == 'A')
                    f0[i][j] = 1;
                if (a[i][j] == 'T')
                    f1[i][j] = 1;
                if (a[i][j] == 'C')
                    f2[i][j] = 1;
                if (a[i][j] == 'G')
                    f3[i][j] = 1;
            }
    if (k >= 50)
    {
        for (int i = 1; i <= n; i++)
        {
            vector<int> alti;
            for (int j = 1; j <= n; j++)
                if (j != i)
                    alti.push_back(j);
            shuffle(alti.begin(), alti.end(), default_random_engine(rng()));
            bool ok = true;
            for (auto it : alti)
            {
                if (!mna(i, it))
                {
                    ok = false;
                    break;
                }
            }
            if (ok)
            {
                cout << i;
                return 0;
            }
        }
    }
    else
    {
        for (int i = 1; i <= n; i++)
            candi[i] = true;
        int cur = 1;
        for (int i = 1; i <= n; i++)
            df[i] = ff(1, i);
        while (true)
        {
            //cout << cur << endl;
            bool nah = false;
            for (int i = 1; i <= n; i++)
                if (i != cur and df[i] != k)
                    nah = true;
            if (!nah)
            {
                cout << cur;
                return 0;
            }
            for (int i = 1; i <= n; i++)
            {
                if (df[i] != k)
                    candi[i] = false;
            }
            for (int i = 1; i <= n; i++)
                if (df[i] == k and candi[i])
                {
                    int mv = i;
                    muta(cur, mv);
                    cur = mv;
                    break;
                }
        }
    }
    return 0;
}

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