Submission #894933

#	Time	Username	Problem	Language	Result	Execution time	Memory
894933		mdub	Genetics (BOI18_genetics)	C++14	100 / 100	595 ms	575912 KiB

genetics

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef unsigned __int128 i128;
LL MOD = 1e9 + 7;

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 () {
  int t = 1;
  
  for (int iT = 0; iT < t; iT++) {
    for (int stuff = 0; stuff < N; stuff++) weights[stuff] = 0;
    for (int y = 0; y < N; y++) {
      for (int x = 0; x < M; x++) {
	prefA[y][x] = 0;
	prefC[y][x] = 0;
	prefG[y][x] = 0;
	prefT[y][x] = 0;
      }
    }total = 0;
  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] = rand() % int(1e9);
    if (weights[i] == 0) {
      cout  << "hey";
      weights[i] += rand() + 2;
    }
    total += weights[i];
    
    
  }
  
  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];
    }
  }
  /*cout << "A:\n";
  for (int y = 0; y < n; y++) {
    for (int x = 0; x < m; x++) {
      cout << prefA[y][x] << "|";
    }
    cout << '\n';
  }
  cout << "C:\n";
  for (int y = 0; y < n; y++) {
    for (int x = 0; x < m; x++) {
      cout << prefC[y][x] << "|";
    }
    cout << '\n';
  }
  cout << "G:\n";
  for (int y = 0; y < n; y++) {
    for (int x = 0; x < m; x++) {
      cout << prefG[y][x] << "|";
    }
    cout << '\n';
  }
  cout << "T:\n";
  for (int y = 0; y < n; y++) {
    for (int x = 0; x < m; x++) {
      cout << prefT[y][x] << "|";
    }
    cout << '\n';
    }*/
  
  LL temp;
  bool ok = false;
  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 > 1e9) cout << "hullo";
    //if (y ==0) cout << "temp: " << LL(temp%MOD) << '\n';
    //if (y ==0) cout << "tot\n:" << LL(((i128(total) - i128(weights[y]))*(i128(k)))%MOD);
    if (temp < 0 || (total - weights[y])*k < 0) cout << "PB\n";
    if (temp == (total - weights[y])*k) {
      cout << y + 1 << '\n';
      ok = true;
      break;
    }
  }
  
  }	
  
}

Compilation message (stderr)

genetics.cpp: In function 'int main()':
genetics.cpp:98:8: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
   98 |   bool ok = false;
      |        ^~

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