Submission #1090834

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090834		andrei_iorgulescu	Genetics (BOI18_genetics)	C++14	27 / 100	2078 ms	9440 KiB

genetics

#include <bits/stdc++.h>

using namespace std;

mt19937 rng(123456);

int n, m, k;
char a[4105][4105];
bitset<4105> bs[4105];

int ff(int x, int y)
{
    int cnt = 0;
    for (int i = 1; i <= m; i++)
        if (a[x][i] != a[y][i])
            cnt++;
    return cnt;
}

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

bool candii[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]++;
        }
    }
}

bool incandi[4105], dl[4105];
vector<int> candi;

int cauta(int x)
{
    for (int i = 0; i < candi.size(); i++)
        if (candi[i] == x)
            return 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];
    if (k >= 200)
    {
        for (int i = 1; i <= n; i++)
            candi.push_back(i), incandi[i] = true;
        while (candi.size() > 1)
        {
            int idx = rng() % candi.size();
            int x = candi[idx], y = -1;
            bool nah = false;
            for (int i = 1; i <= n; i++)
            {
                if (dl[i])
                    continue;
                if (x != i and !mna(x, i))
                {
                    nah = true;
                    y = i;
                    break;
                }
            }
            if (y == -1)
            {
                cout << x;
                return 0;
            }
            candi.erase(candi.begin() + idx);
            if (incandi[y])
                candi.erase(candi.begin() + cauta(y));
            //cout << x << ' ' << y << endl;
            incandi[x] = incandi[y] = false;
            dl[x] = dl[y] = true;
            vector<int> deel;
            for (auto it : candi)
            {
                if (!mna(it, y) or !mna(it, x))
                    deel.push_back(it);
            }
            for (auto it : deel)
                candi.erase(candi.begin() + cauta(it)), incandi[it] = false;
        }
        cout << candi[0];
    }
    else
    {
        for (int i = 1; i <= n; i++)
            candii[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)
                    candii[i] = false;
            }
            for (int i = 1; i <= n; i++)
                if (df[i] == k and candii[i])
                {
                    int mv = i;
                    muta(cur, mv);
                    cur = mv;
                    break;
                }
        }
    }
    return 0;
}

Compilation message (stderr)

genetics.cpp: In function 'int cauta(int)':
genetics.cpp:56:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for (int i = 0; i < candi.size(); i++)
      |                     ~~^~~~~~~~~~~~~~
genetics.cpp: In function 'int main()':
genetics.cpp:78:18: warning: variable 'nah' set but not used [-Wunused-but-set-variable]
   78 |             bool nah = false;
      |                  ^~~
genetics.cpp: In function 'int cauta(int)':
genetics.cpp:59:1: warning: control reaches end of non-void function [-Wreturn-type]
   59 | }
      | ^

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