Submission #1090351

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090351		andrei_iorgulescu	Genetics (BOI18_genetics)	C++14	46 / 100	2015 ms	31056 KiB

genetics

#include <bits/stdc++.h>

using namespace std;

mt19937 rng(8962);

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

bool mna(int x, int y)
{
    if (n <= 100)
    {
        int df = 0;
        for (int i = 1; i <= m; i++)
            if (a[x][i] != a[y][i])
                df++;
        if (df == k)
            return true;
        return false;
    }
    else
    {
        if ((bs[x] ^ bs[y]).count() == k)
            return true;
        return false;
    }
}

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] == 'C')
                bs[i][j] = 1;
    vector<int> candi;
    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;
        int cate = 0;
        for (auto it : alti)
        {
            if (!mna(i, it))
            {
                ok = false;
                break;
            }
            cate++;
            if (cate == 300)
                break;
        }
        if (ok)
            candi.push_back(i);
    }
    vector<int> candi2;
    for (auto i : candi)
    {
        vector<int> alti;
        for (auto j : candi)
            if (j != i)
                alti.push_back(j);
        shuffle(alti.begin(), alti.end(), default_random_engine(rng()));
        bool ok = true;
        int cate = 0;
        for (auto it : alti)
        {
            if (!mna(i, it))
            {
                ok = false;
                break;
            }
        }
        if (ok)
            candi2.push_back(i);
    }
    if (candi2.size() == 1)
    {
        cout << candi2[0];
        return 0;
    }
    for (auto i : candi2)
    {
        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;
        int cate = 0;
        for (auto it : alti)
        {
            if (!mna(i, it))
            {
                ok = false;
                break;
            }
        }
        if (ok)
        {
            cout << i;
            return 0;
        }
    }
    return 0;
}

Compilation message (stderr)

genetics.cpp: In function 'bool mna(int, int)':
genetics.cpp:25:37: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   25 |         if ((bs[x] ^ bs[y]).count() == k)
      |             ~~~~~~~~~~~~~~~~~~~~~~~~^~~~
genetics.cpp: In function 'int main()':
genetics.cpp:77:13: warning: unused variable 'cate' [-Wunused-variable]
   77 |         int cate = 0;
      |             ^~~~
genetics.cpp:102:13: warning: unused variable 'cate' [-Wunused-variable]
  102 |         int cate = 0;
      |             ^~~~

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