제출 #1214014

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1214014		aykhn	Genetics (BOI18_genetics)	C++20	100 / 100	294 ms	19968 KiB

genetics

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define inf 0x3F3F3F3F3F3F3F3F

const int MXN = 5e3 + 1;
const int mod = 1e9 + 7;

int val[MXN];
int mp[1000];
int id[MXN][4];

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

signed main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  mp['A'] = 0, mp['C'] = 1, mp['G'] = 2, mp['T'] = 3;
  int n, m, k;
  cin >> n >> m >> k;
  for (int i = 0; i < n; i++) val[i] = rng() % mod;
  string s[n];
  for (int i = 0; i < n; i++) 
  {
    cin >> s[i];
    for (int j = 0; j < m; j++)
    {
      int x = mp[s[i][j]];
      id[j][x] = (id[j][x] + val[i]) % mod;
    }
  }
  for (int i = 0; i < n; i++)
  {
    int need = 0, have = 0;
    for (int j = 0; j < n; j++)
    {
      if (i != j) need = (need + val[j] * k % mod) % mod;
    }
    for (int j = 0; j < m; j++)
    {
      for (int x = 0; x < 4; x++)
      {
        if (x != mp[s[i][j]]) have = (have + id[j][x]) % mod;
      }
    }
    if (have == need)
    {
      cout << i + 1 << '\n';
      return 0;
    }
  }
  assert(0);
}

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