Submission #879758

#	Time	Username	Problem	Language	Result	Execution time	Memory
879758		iskhakkutbilim	Genetics (BOI18_genetics)	C++17	100 / 100	890 ms	149424 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:14: 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:20: 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