Submission #1249231

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249231		yoshi_33550336	Genetics (BOI18_genetics)	C++20	100 / 100	679 ms	28240 KiB

genetics

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#ifndef yoshi_likes_e4
#define endl '\n'
#endif
#define problem ""
#define multitest 0
#define debug(x) cerr << #x << " = " << x << endl;
void init()
{
}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
string A[4100];
bitset<4100> Ab[4][4100];
int C[256];
int cnt[4101];
int c[4][4100];
void Yoshi()
{
    C['A'] = 0;
    C['T'] = 1;
    C['C'] = 2;
    C['G'] = 3;
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++)
        cin >> A[i];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            Ab[C[A[i][j]]][i][j] = 1, c[C[A[i][j]]][j]++;
    vector<int> cands, ord;
    for (int i = 0; i < n; i++)
    {
        int r = 0;
        for (int j = 0; j < m; j++)
            r += n - c[C[A[i][j]]][j];
        if (r == k * (n - 1))
            cands.push_back(i);
        ord.push_back(i);
    }
    shuffle(cands.begin(), cands.end(), rng);
    for (auto &i : cands)
    {
        bool ck = 1;
        for (auto &j : ord)
        {
            if (m - ((Ab[0][j] & Ab[0][i]) | (Ab[1][j] & Ab[1][i]) | (Ab[2][j] & Ab[2][i]) | (Ab[3][j] & Ab[3][i]))
                            .count() !=
                    k &&
                i != j)
            {
                ck = 0;
                break;
            }
        }
        if (ck)
            cout << i + 1 << endl, exit(0);
    }
}

signed main()
{
#ifndef yoshi_likes_e4
    ios::sync_with_stdio(0);
    if (fopen(problem ".inp", "r"))
    {
        freopen(problem ".inp", "r", stdin);
        freopen(problem ".out", "w", stdout);
    }
#endif
    init();
    int t = 1;
#if multitest
    fin >> t;
#endif
    while (t--)
        Yoshi();
}

Compilation message (stderr)

genetics.cpp: In function 'int main()':
genetics.cpp:68:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         freopen(problem ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
genetics.cpp:69:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         freopen(problem ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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