Submission #203081

#	Time	Username	Problem	Language	Result	Execution time	Memory
203081		quocnguyen1012	Genetics (BOI18_genetics)	C++14	100 / 100	683 ms	82808 KiB

genetics

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;

const int mod = 1e9 + 7, maxn = 4105, base = 131;

int f[maxn][5];
int a[maxn][maxn];
int N, M, K;
int POW[maxn];

int to(char x)
{
  if (x == 'A') return 1;
  if (x == 'C') return 2;
  if (x == 'G') return 3;
  else return 4;
}

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  if (fopen("A.INP", "r")){
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  }
  POW[0] = 1;
  for (int i = 1; i < maxn; ++i){
    POW[i] = 1ll * POW[i - 1] * base % mod;
  }
  cin >> N >> M >> K;
  for (int i = 1; i <= N; ++i){
    for (int j = 1; j <= M; ++j){
      char x; cin >> x;
      a[i][j] = to(x);
      f[j][a[i][j]] += POW[i];
      f[j][a[i][j]] %= mod;
    }
  }
  for (int i = 1; i <= N; ++i){
    ll need = 0, cur = 0;
    for (int j = 1; j <= N; ++j){
      if (j != i) need += 1ll * K * POW[j] % mod;
    }
    for (int j = 1; j <= M; ++j){
      for (int k = 1; k <= 4; ++k){
        if (k != a[i][j]){
          cur += f[j][k];
        }
      }
    }
    need %= mod; cur %= mod;
    if (cur == need){
      cout << i;
      return 0;
    }
  }
}

Compilation message (stderr)

genetics.cpp: In function 'int main()':
genetics.cpp:30:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.INP", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
genetics.cpp:31:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.OUT", "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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