Submission #202903

#	Time	Username	Problem	Language	Result	Execution time	Memory
202903		admin	Genetics (BOI18_genetics)	C++14	100 / 100	376 ms	17072 KiB

genetics

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
const int N = 4105;
const ll P = 9949, Q = int(1e9) + 9;
 
int n, m, k;
char s[N][N];
ll c[5][N], p[N], r;
 
int main(){
    scanf("%d%d%d", &n, &m, &k);
    ll t = 1;
    for(int i = 1; i <= n; i++){
        scanf("%s", s[i]);
        for(int j = 0; j < m; j++){
            s[i][j] = (s[i][j] == 'A' ? 1 : s[i][j] == 'C' ? 2 :
                s[i][j] == 'G' ? 3 : 4);
            c[s[i][j]][j] = (c[s[i][j]][j] + t) % Q;
            c[0][j] = (c[0][j] + t) % Q;
        }
        r = (r + t * k) % Q;
        p[i] = t;
        t = t * P % Q;
    }
    for(int i = 1; i <= n; i++){
        ll t = 0;
        for(int j = 0; j < m; j++){
            t = (t + c[0][j] - c[s[i][j]][j] + Q) % Q;
        }
        if((t + p[i] * k) % Q == r){ printf("%d\n", i); return 0; }
    }
}

Compilation message (stderr)

genetics.cpp: In function 'int main()':
genetics.cpp:21:22: warning: array subscript has type 'char' [-Wchar-subscripts]
             c[s[i][j]][j] = (c[s[i][j]][j] + t) % Q;
                      ^
genetics.cpp:21:39: warning: array subscript has type 'char' [-Wchar-subscripts]
             c[s[i][j]][j] = (c[s[i][j]][j] + t) % Q;
                                       ^
genetics.cpp:31:41: warning: array subscript has type 'char' [-Wchar-subscripts]
             t = (t + c[0][j] - c[s[i][j]][j] + Q) % Q;
                                         ^
genetics.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &m, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
genetics.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", s[i]);
         ~~~~~^~~~~~~~~~~~

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