oj.uz

Submission #894605

# Submission time Handle Problem Language Result Execution time Memory
894605 2023-12-28T14:20:20 Z mdub Genetics (BOI18_genetics) C++14
0 / 100
 128 ms 205864 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 17244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 128 ms 205864 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 128 ms 205864 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 17244 KB Output isn't correct
2 Halted 0 ms 0 KB -