| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1268605 | ducdev | Genetics (BOI18_genetics) | C++17 | 0 ms | 0 KiB |
// Author: 4uckd3v - Nguyen Cao Duc
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
typedef long long ll;
const int MAX_N = 4100;
const int MOD = 1e9 + 7;
int m, n, k;
char a[MAX_N + 5][MAX_N + 5];
namespace SUBTASK_1 {
const int LIM = 100;
int diff(int i, int j) {
int cnt = 0;
for (int k = 1; k <= n; k++)
if (a[i][k] != a[j][k]) cnt++;
return cnt;
};
void Solve() {
for (int i = 1; i <= m; i++) {
bool real = true;
for (int j = 1; j <= m; j++) {
if (i == j) continue;
if (diff(i, j) != k) {
real = false;
break;
};
};
if (real) {
cout << i << '\n';
break;
};
};
};
}; // namespace SUBTASK_1
namespace SUBTASK_23 {
const int M = MAX_N;
const int N = MAX_N;
int canReal[M + 5];
int cache[M + 5][M + 5];
bitset<N> bs[M];
bool checkSubtask() {
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
if (a[i][j] != 'A' && a[i][j] != 'C') return false;
return true;
};
void Solve() {
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
bs[i - 1].set(j - 1, a[i][j] == 'A');
};
};
memset(cache, -1, sizeof cache);
for (int i = 0; i <= m; i++) canReal[i] = true;
for (int i = 0; i < m; i++) {
if (!canReal[i]) continue;
for (int j = 0; j < m; j++) {
if (i == j) continue;
if (cache[i][j] == -1) cache[i][j] = cache[j][i] = (bs[i] ^ bs[j]).count();
if (cache[i][j] != k) {
canReal[i] = canReal[j] = false;
break;
};
};
if (canReal[i]) {
cout << i + 1 << '\n';
break;
};
};
};
}; // namespace SUBTASK_23
int numCorrect = 0;
for (int type = 0; type < 4; type++) {
numCorrect += (bs[1][type] & bs[i][type]).count();
if (numCorrect > n - k) break;
};
cache[0][i] = cache[0][1] = numCorrect;
if (numCorrect != n - k)
canReal[0] = canReal[i] = false;
};
};
for (int i = 0; i < m; i++)
if (canReal[i]) candidates.push_back(i);
for (int i : candidates) {
if (!canReal[i]) continue;
for (int j : candidates) {
if (i == j) continue;
if (cache[i][j] == -1) {
int numCorrect = 0;
for (int type = 0; type < 4; type++) {
numCorrect += (bs[i][type] & bs[j][type]).count();
if (numCorrect > n - k) break;
};
cache[i][j] = cache[j][i] = numCorrect;
};
if (cache[i][j] != n - k) {
canReal[i] = canReal[j] = false;
break;
};
};
if (canReal[i]) {
cout << i + 1 << '\n';
break;
};
};
};
}; // namespace SUBTASK_4
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
if (fopen("MAIN.INP", "r")) {
freopen("MAIN.INP", "r", stdin);
freopen("MAIN.OUT", "w", stdout);
};
cin >> m >> n >> k;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
};
};
if (m <= 100 && n <= 100)
return SUBTASK_1::Solve(), 0;
if (SUBTASK_23::checkSubtask())
return SUBTASK_23::Solve(), 0;
SUBTASK_4::Solve();
};