Submission #855889

#	Time	Username	Problem	Language	Result	Execution time	Memory
855889		lovrot	Genetics (BOI18_genetics)	C++17	100 / 100	897 ms	149664 KiB

genetics

#include <cstdio> 
#include <random> 
#include <chrono> 

using namespace std;

typedef long long ll; 

const int N = 4110;
const ll INF = 1e18;
//const ll INF = 10;

int n, m, k;
ll A[N][N];

ll W[N] = {3, 2, 1, 9}, C[N][10];

int main() {
  	mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  	scanf("%d%d%d", &n, &m, &k);
  	ll sum = 0;
  	for(int i = 0; i < n; ++i) {	
        W[i] = rng() % INF;	
        sum += W[i];
       // printf("%lld\n", W[i]);
    }
  	for(int i = 0; i < n; ++i)
      	for(int j = 0; j < m; ++j) {	
          	char c;
        	scanf(" %c", &c);
          	A[i][j] = c == 'A' ? 0 : (c == 'C' ? 1 : (c == 'G' ? 2 : 3));
           // printf("%d%c", A[i][j], " \n"[j == m - 1]);
        }
	for(int j = 0; j < m; ++j)  	
      	for(int i = 0; i < n; ++i)
          	for(int l = 0; l < 4; ++l) C[j][l] += A[i][j] != l ? W[i] : 0;
  	for(int i = 0; i < n; ++i) {
      	ll _sum = 0;
      	for(int j = 0; j < m; ++j) _sum += C[j][A[i][j]];
        //printf("%lld %lld\n", _sum, (sum - W[i]) * k);
      	if(_sum == (sum - W[i]) * (ll) k) {
          	printf("%d\n", i + 1);
          	return 0;
        }
    }
  	return 0;
}

Compilation message (stderr)

genetics.cpp: In function 'int main()':
genetics.cpp:20:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |    scanf("%d%d%d", &n, &m, &k);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~
genetics.cpp:30:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |          scanf(" %c", &c);
      |          ~~~~~^~~~~~~~~~~

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