Submission #202894

#	Time	Username	Problem	Language	Result	Execution time	Memory
202894		karma	Genetics (BOI18_genetics)	C++14	100 / 100	467 ms	17144 KiB

genetics

#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
 
long long sum[4110][5];
char a[4110][4110];
 
int convert (char c){
    if (c == 'A')
        return 0;
    if (c == 'C')
        return 1;
    if (c == 'G')
        return 2;
    return 3;
}
int check (int x , int n , int m, int k){
 
    int i , j , dif;
 
    for (i=1;i<=n;i++){
        if (i == x)
            continue;
        dif = 0;
        for (j=1;j<=m;j++){
            if (a[x][j] != a[i][j])
                dif++;
            if (dif > k)
                return 0;
        }
        if (dif != k)
            return 0;
    }
    return 1;
 
}
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n , m , k , i , j , curr , summ;
    fscanf (fin,"%d%d%d\n",&n,&m,&k);
    for (i=1;i<=n;i++){
        fgets (a[i] + 1 , 5000 , fin);
        for (j=1;j<=m;j++){
            sum[j][convert(a[i][j])] = (sum[j][convert(a[i][j])] + i)%MOD;
        }
    }
    for (curr = 1 ; curr <= n ; curr ++){
        summ = 0;
        for (i=1;i<=m;i++){
 
            summ = (summ + sum[i][0] + sum[i][1] + sum[i][2] + sum[i][3])%MOD;
            summ = ((summ - sum[i][convert(a[curr][i])]) % MOD + MOD )%MOD;
 
        }
 
        if (summ == (((long long) k * ( ( ((long long)n * (n+1)) / 2 ) %MOD - curr)%MOD )%MOD + MOD)%MOD && check(curr , n, m , k)) {
            fprintf (fout,"%d ",curr);
            return 0;
        }
 
    }
    return 0;
}

Compilation message (stderr)

genetics.cpp: In function 'int main()':
genetics.cpp:42:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d%d%d\n",&n,&m,&k);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
genetics.cpp:44:15: warning: ignoring return value of 'char* fgets(char*, int, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         fgets (a[i] + 1 , 5000 , fin);
         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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