Submission #421095

#	Time	Username	Problem	Language	Result	Execution time	Memory
421095		nicolaalexandra	Genetics (BOI18_genetics)	C++14	100 / 100	988 ms	101084 KiB

genetics

#include <bits/stdc++.h>
#define DIM 4200
#pragma GCC optimize("Ofast")
using namespace std;

char s[DIM];
int a[DIM][DIM];
long long sum[DIM][DIM],r[DIM];
int n,m,k,i,j;

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>m>>k;
    for (i=1;i<=n;i++){
        cin>>s+1;
        for (j=1;j<=m;j++){
            if (s[j] == 'A')
                a[i][j] = 1;
            if (s[j] == 'C')
                a[i][j] = 2;
            if (s[j] == 'G')
                a[i][j] = 3;
            if (s[j] == 'T')
                a[i][j] = 4;
        }
    }

    long long total = 0;
    for (i=1;i<=n;i++){
        r[i] = rand();
        total += r[i];

        for (j=1;j<=m;j++)
            sum[j][a[i][j]] += r[i];
    }

    for (i=1;i<=n;i++){

        long long val = 0;
        for (j=1;j<=m;j++)
            val += total - sum[j][a[i][j]];

        if (val == 1LL * k * (total - r[i])){
            cout<<i;
            break;
        }
    }


    /*for (int pas=1;pas<=4;pas++){

        for (i=1;i<=n;i++){
            v[i].reset();
            for (j=1;j<=m;j++){
                if (a[i][j] == ch[pas])
                    v[i][j] = 1;
            }}

        for (i=1;i<=n;i++)
            for (j=i+1;j<=n;j++){
                int val = (v[i] & v[j]).count();
                //int val = __builtin_popcount (v[i] & v[j]);
                cnt[i][j] += val;
                cnt[j][i] += val;
            }
    }

    for (i=1;i<=n;i++){
        int ok = 1;
        for (j=1;j<=n;j++)
            if (i != j && cnt[i][j] != m - k){
                ok = 0;
                break;
            }
        if (ok){
            cout<<i;
            break;
        }
    }

*/

    return 0;
}

Compilation message (stderr)

genetics.cpp: In function 'int main()':
genetics.cpp:18:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   18 |         cin>>s+1;
      |              ~^~

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