Submission #252786

#	Time	Username	Problem	Language	Result	Execution time	Memory
252786		evpipis	Genetics (BOI18_genetics)	C++11	100 / 100	649 ms	82936 KiB

genetics

#include <bits/stdc++.h>
using namespace std;

const int len = 4105, base = 53, mod = 1e9+7;
char str[len];
int arr[len][len], col[len][4], po[len];

int add(int a, int b){
    return (a+b)%mod;
}

int mul(int a, int b){
    return (a*1LL*b)%mod;
}

int to(char a){
    if (a == 'A') return 0;
    if (a == 'C') return 1;
    if (a == 'G') return 2;
    return 3;
}

int main(){
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 0; i < n; i++){
        scanf("%s", &str);
        for (int j = 0; j < m; j++)
            arr[i][j] = to(str[j]);
    }

    po[0] = 1;
    for (int i = 1; i < n; i++)
        po[i] = mul(po[i-1], base);

    for (int j = 0; j < m; j++){
        for (int i = 0; i < n; i++)
            col[j][arr[i][j]] = add(col[j][arr[i][j]], po[i]);
    }

    for (int i = 0; i < n; i++){
        int all = 0, cur = 0;

        for (int j = 0; j < n; j++)
            if (i != j)
                all = add(all, mul(k, po[j]));

        for (int j = 0; j < m; j++)
            for (int l = 0; l < 4; l++)
                if (arr[i][j] != l)
                    cur = add(cur, col[j][l]);

        //printf("i = %d, all = %d, cur = %d\n", i, all, cur);

        if (cur == all){
            printf("%d\n", i+1);
            return 0;
        }
    }

    return 0;
}

Compilation message (stderr)

genetics.cpp: In function 'int main()':
genetics.cpp:27:25: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[4105]' [-Wformat=]
         scanf("%s", &str);
                     ~~~~^
genetics.cpp:25: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:27:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", &str);
         ~~~~~^~~~~~~~~~~~

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