Submission #1249237

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249237		yoshi_33550336	Genetics (BOI18_genetics)	C++20	100 / 100	303 ms	25892 KiB

genetics

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt,tune=native")
#include <bits/stdc++.h>
namespace fastio
{
    static constexpr size_t buf_size = 1 << 18;
    static constexpr size_t integer_size = 20;
    static constexpr size_t block_size = 10000;

    static char inbuf[buf_size + 1] = {};
    static char outbuf[buf_size + 1] = {};
    static char block_str[block_size * 4 + 1] = {};

    static constexpr uint64_t power10[] = {1,
                                           10,
                                           100,
                                           1000,
                                           10000,
                                           100000,
                                           1000000,
                                           10000000,
                                           100000000,
                                           1000000000,
                                           10000000000,
                                           100000000000,
                                           1000000000000,
                                           10000000000000,
                                           100000000000000,
                                           1000000000000000,
                                           10000000000000000,
                                           100000000000000000,
                                           1000000000000000000,
                                           10000000000000000000u};

    struct Scanner
    {
    private:
        size_t pos, end;

        void load()
        {
            end = fread(inbuf, 1, buf_size, stdin);
            inbuf[end] = '\0';
        }
        void reload()
        {
            size_t len = end - pos;
            memmove(inbuf, inbuf + pos, len);
            end = len + fread(inbuf + len, 1, buf_size - len, stdin);
            inbuf[end] = '\0';
            pos = 0;
        }
        void skip_space()
        {
            while (inbuf[pos] <= ' ')
            {
                if (__builtin_expect(++pos == end, 0))
                    reload();
            }
        }
        char get_next()
        {
            return inbuf[pos++];
        }
        char get_next_nonspace()
        {
            skip_space();
            return inbuf[pos++];
        }

    public:
        Scanner()
        {
            load();
        }

        void scan(char &c)
        {
            c = get_next_nonspace();
        }
        void scan(std::string &s)
        {
            skip_space();
            s = "";
            do
            {
                size_t start = pos;
                while (inbuf[pos] > ' ')
                    pos++;
                s += std::string(inbuf + start, inbuf + pos);
                if (inbuf[pos] != '\0')
                    break;
                reload();
            } while (true);
        }

        template <class T>
        typename std::enable_if<std::is_integral<T>::value, void>::type scan(T &x)
        {
            char c = get_next_nonspace();
            if (__builtin_expect(pos + integer_size >= end, 0))
                reload();
            bool neg = false;
            if (c == '-')
                neg = true, x = 0;
            else
                x = c & 15;
            while ((c = get_next()) >= '0')
                x = x * 10 + (c & 15);
            if (neg)
                x = -x;
        }

        template <class Head, class... Others>
        void scan(Head &head, Others &...others)
        {
            scan(head);
            scan(others...);
        }

        template <class T>
        Scanner &operator>>(T &x)
        {
            scan(x);
            return *this;
        }
    };

    struct Printer
    {
    private:
        size_t pos = 0;

        void flush()
        {
            fwrite(outbuf, 1, pos, stdout);
            pos = 0;
        }

        void pre_calc()
        {
            for (size_t i = 0; i < block_size; i++)
            {
                size_t j = 4, k = i;
                while (j--)
                {
                    block_str[i * 4 + j] = k % 10 + '0';
                    k /= 10;
                }
            }
        }

        static constexpr size_t get_integer_size(uint64_t n)
        {
            if (n >= power10[10])
            {
                if (n >= power10[19])
                    return 20;
                if (n >= power10[18])
                    return 19;
                if (n >= power10[17])
                    return 18;
                if (n >= power10[16])
                    return 17;
                if (n >= power10[15])
                    return 16;
                if (n >= power10[14])
                    return 15;
                if (n >= power10[13])
                    return 14;
                if (n >= power10[12])
                    return 13;
                if (n >= power10[11])
                    return 12;
                return 11;
            }
            else
            {
                if (n >= power10[9])
                    return 10;
                if (n >= power10[8])
                    return 9;
                if (n >= power10[7])
                    return 8;
                if (n >= power10[6])
                    return 7;
                if (n >= power10[5])
                    return 6;
                if (n >= power10[4])
                    return 5;
                if (n >= power10[3])
                    return 4;
                if (n >= power10[2])
                    return 3;
                if (n >= power10[1])
                    return 2;
                return 1;
            }
        }

    public:
        Printer()
        {
            pre_calc();
        }
        ~Printer()
        {
            flush();
        }

        void print(char c)
        {
            outbuf[pos++] = c;
            if (__builtin_expect(pos == buf_size, 0))
                flush();
        }
        void print(const char *s)
        {
            while (*s != 0)
            {
                outbuf[pos++] = *s++;
                // if (pos == buf_size) flush();
                if (__builtin_expect(pos == buf_size, 0))
                    flush();
            }
        }
        void print(const std::string &s)
        {
            for (auto c : s)
            {
                outbuf[pos++] = c;
                // if (pos == buf_size) flush();
                if (__builtin_expect(pos == buf_size, 0))
                    flush();
            }
        }

        template <class T>
        typename std::enable_if<std::is_integral<T>::value, void>::type print(T x)
        {
            if (__builtin_expect(pos + integer_size >= buf_size, 0))
                flush();
            if (x < 0)
                print('-'), x = -x;
            size_t digit = get_integer_size(x);
            size_t len = digit;
            while (len >= 4)
            {
                len -= 4;
                memcpy(outbuf + pos + len, block_str + (x % block_size) * 4, 4);
                x /= block_size;
            }
            memcpy(outbuf + pos, block_str + x * 4 + (4 - len), len);
            pos += digit;
        }

        template <class Head, class... Others>
        void print(const Head &head, const Others &...others)
        {
            print(head);
            print(' ');
            print(others...);
        }

        template <class... Args>
        void println(const Args &...args)
        {
            print(args...);
            print('\n');
        }

        template <class T>
        Printer &operator<<(const T &x)
        {
            print(x);
            return *this;
        }
    };
}; // namespace fastio

fastio::Scanner fin;
fastio::Printer fout;
#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;
    fin >> n >> m >> k;
    for (int i = 0; i < n; i++)
        fin >> 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(ord.begin(), ord.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)
            fout << 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:348:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  348 |         freopen(problem ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
genetics.cpp:349:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  349 |         freopen(problem ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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