Submission #996101

#	Time	Username	Problem	Language	Result	Execution time	Memory
996101		doducanh	Genetics (BOI18_genetics)	C++14	100 / 100	526 ms	48132 KiB

genetics

#include<bits/stdc++.h>
using namespace std;
int n,m,diff_num;

vector<char>DNA{'A','T','C','G'};
string s[4105];
long long eq_dna[4105][4];
main()
{
    cin>>n>>m>>diff_num;
    for(int i=0;i<n;i++){
        cin>>s[i];
    }
    mt19937 gen(42069);
    uniform_int_distribution<> distr(1,INT32_MAX);
    vector<long long>weights(n);
    for(int i=0;i<n;i++){
        weights[i]=distr(gen);
    }
    long long sum=accumulate(weights.begin(),weights.end(),0ll);
    for(int d=0;d<DNA.size();d++){
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                eq_dna[j][d]+=((s[i][j]==DNA[d])*weights[i]);
            }
        }
    }
    for(int i=0;i<n;i++){
        long long tmp=0;
        for(int d=0;d<4;d++){
            for(int j=0;j<m;j++){
                if(s[i][j]==DNA[d])tmp+=(sum-eq_dna[j][d]);
            }
        }
        if(tmp==diff_num*(sum-weights[i]))return cout<<i+1,0;
    }
    return 0;
}

Compilation message (stderr)

genetics.cpp:8:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    8 | main()
      | ^~~~
genetics.cpp: In function 'int main()':
genetics.cpp:21:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(int d=0;d<DNA.size();d++){
      |                 ~^~~~~~~~~~~

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