Submission #993268

#	Time	Username	Problem	Language	Result	Execution time	Memory
993268		caterpillow	Genetics (BOI18_genetics)	C++17	100 / 100	348 ms	83176 KiB

genetics

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pl = pair<ll, ll>;
using pi = pair<int, int>;
#define vt vector
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end() 
#define sz(x) ((int) (x).size())
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0R(i, b) FOR (i, 0, b)
#define endl '\n'
const ll INF = 1e18;
const int inf = 1e9;

random_device rd;
mt19937 mt(rd());

main() {
    cin.tie(0)->sync_with_stdio(0);

    int n, m, k; cin >> n >> m >> k;
    vt<vt<int>> seqs(n, vt<int>(m));
    F0R (i, n) {
        string st; cin >> st;
        F0R (j, m) {
            if (st[j] == 'A') seqs[i][j] = 0;
            else if (st[j] == 'C') seqs[i][j] = 1;
            else if (st[j] == 'T') seqs[i][j] = 2;
            else if (st[j] == 'G') seqs[i][j] = 3;
        }
    }

    vt<ll> magic(n); 
    F0R (i, n) magic[i] = mt();

    vt<ll> sum(n);
    F0R (j, m) {
        vt<ll> bruh(4);
        F0R (i, n) bruh[seqs[i][j]] += magic[i];
        ll tot = accumulate(all(bruh), 0ll);
        F0R (i, n) sum[i] += tot - bruh[seqs[i][j]];
    }

    ll balls = accumulate(all(magic), 0ll);
    F0R (i, n) {
        if (sum[i] == k * (balls - magic[i])) {
            cout << i + 1 << endl;
            return 0;
        }
    }
}

Compilation message (stderr)

genetics.cpp:24:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   24 | main() {
      | ^~~~

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