Submission #1090832

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090832		andrei_iorgulescu	Genetics (BOI18_genetics)	C++14	27 / 100	2067 ms	13916 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 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];
    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];
    return 0;
}

Compilation message (stderr)

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

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