Submission #894605

#	Time	Username	Problem	Language	Result	Execution time	Memory
894605		mdub	Genetics (BOI18_genetics)	C++14	0 / 100	128 ms	205864 KiB

genetics

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef __int128 i128;
LL MOD = 1e18 + rand()%1000;

const int N = 4100 + 5;
const int M = 4100 + 5;
int n, m, k;
string a[N];
LL prefA[N+1][M];
LL prefC[N+1][M];
LL prefG[N+1][M];
LL prefT[N+1][M];
LL weights[N];
LL total;
int main () {
  srand(42);
  
  cin >> n >> m >> k;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  
  for (int i =0 ; i < n; i++) {
    weights[i] = LL(rand())* LL(1e8) + rand();
    total += weights[i];
    total %= MOD;
  }
  
  for (int x = 0; x < m; x++) {
    if (a[0][x] == 'A') prefA[0][x] = weights[0];
    if (a[0][x] == 'C') prefC[0][x] = weights[0];
    if (a[0][x] == 'G') prefG[0][x] = weights[0];
    if (a[0][x] == 'T') prefT[0][x] = weights[0];
  }
  for (int y = 1; y < n; y++) {
    for (int x = 0; x < m; x++) {
      prefA[y][x] = prefA[y-1][x];
      prefC[y][x] = prefC[y-1][x];
      prefG[y][x] = prefG[y-1][x];
      prefT[y][x] = prefT[y-1][x];
      if (a[y][x] == 'A') prefA[y][x] += weights[y];
      if (a[y][x] == 'C') prefC[y][x] += weights[y];
      if (a[y][x] == 'G') prefG[y][x] += weights[y];
      if (a[y][x] == 'T') prefT[y][x] += weights[y];
      prefA[y][x] %= MOD;
      prefC[y][x] %= MOD;
      prefG[y][x] %= MOD;
      prefT[y][x] %= MOD;
    }
  }
  i128 temp;
  for (int y = 0; y < n; y++) {
    temp = 0;
    for (int x = 0; x < m; x++) {
      if (a[y][x] == 'A') {
	temp += total - prefA[n-1][x];
      }
      else if (a[y][x] == 'C') {
	temp += total - prefC[n-1][x];
      }
      else if (a[y][x] == 'G') {
	temp += total - prefG[n-1][x];
      }
      else if (a[y][x] == 'T') {
	temp += total - prefT[n-1][x];
      }
      

    }
    if (temp == (i128(total) - i128(weights[y]))*(i128(k))) {
      cout << y + 1 << '\n';
      return 0;
    }
  }
    	
  
}

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