Submission #202907

#	Time	Username	Problem	Language	Result	Execution time	Memory
202907		admin	Genetics (BOI18_genetics)	C++14	100 / 100	338 ms	17144 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(){
	cin.sync_with_stdio(false);
  cin>>n>>m>>k;   ll t = 1;
    for(int i = 1; i <= n; i++){cin>>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:20:22: warning: array subscript has type 'char' [-Wchar-subscripts]
             c[s[i][j]][j] = (c[s[i][j]][j] + t) % Q;
                      ^
genetics.cpp:20:39: warning: array subscript has type 'char' [-Wchar-subscripts]
             c[s[i][j]][j] = (c[s[i][j]][j] + t) % Q;
                                       ^
genetics.cpp:30:41: warning: array subscript has type 'char' [-Wchar-subscripts]
             t = (t + c[0][j] - c[s[i][j]][j] + Q) % Q;
                                         ^

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