제출 #1359536

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1359536		domi	Genetics (BOI18_genetics)	C++20	100 / 100	840 ms	20844 KiB

genetics

#include <bits/stdc++.h>

#define int long long
#define fi first
#define se second

#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()

#define lsb(x) (x & (-x))
#define vi vector<int>
#define YES { cout << "YES" << endl; return; }
#define NO { cout << "NO" << endl; return; }

using ll = long long;
using pii = std::pair<int, int>;

const int NMAX = 5e3;
const int SIGMA = 4;

using namespace std;

mt19937 rng(time(NULL));
char s[NMAX + 5][NMAX + 5];
int cnt[NMAX + 5][SIGMA + 5], rnd[NMAX + 5], n, m, k;

inline int get_id(char ch) {
    return string("AGTC").find(ch);
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m >> k;

    int sum = 0;
    for (int i = 1; i <= n; ++i) {
        rnd[i] = rng();
        for (int j = 1; j <= m; ++j) {
            cin >> s[i][j];
            cnt[j][get_id(s[i][j])] += rnd[i];
        }
        sum += rnd[i];
    }

    int ans = -1;
    for (int i = 1; i <= n; ++i) {
        int ret = 0;
        for (int j = 1; j <= m; ++j) {
            for (int c = 0; c < 4; ++c) {
                if (get_id(s[i][j]) == c) continue;
                ret += cnt[j][c];
            }
        }

        if (ret == (sum - rnd[i]) * k)
            ans = i;
    }

    assert(ans != -1);
    cout << ans << '\n';
    return 0;
}

• 서브태스크 1: 27 / 27
• 서브태스크 2: 19 / 19
• 서브태스크 3: 28 / 28
• 서브태스크 4: 26 / 26