Submission #88709

#	Time	Username	Problem	Language	Result	Execution time	Memory
88709		igzi	Genetics (BOI18_genetics)	C++17	46 / 100	280 ms	26872 KiB

genetics

#include <bits/stdc++.h>
#define maxN 41002

using namespace std;

string s[maxN];
long long a[4][maxN],w[maxN],n,m,k,i,j,sum;
vector <long long> v;

bool moze(int i){
long long tmp=0;
for(int j=0;j<m;j++){
    if(s[i][j]=='A') tmp+=(sum-a[0][j]);
    if(s[i][j]=='C') tmp+=(sum-a[1][j]);
    if(s[i][j]=='G') tmp+=(sum-a[2][j]);
    if(s[i][j]=='T') tmp+=(sum-a[3][j]);
}
return tmp==(sum-w[i])*k;
}
bool jeste(int x){
for(int i=0;i<n;i++){
    if(i==x) continue;
    int tmp=0;
    for(int j=0;j<m;j++){
        if(s[x][j]!=s[i][j]) tmp++;
    }
    if(tmp!=k) return false;
}
return true;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    srand(time(NULL));
    cin>>n>>m>>k;
    for(i=0;i<n;i++){
        w[i]=rand();
        sum+=w[i];
    }
    for(i=0;i<n;i++){
        cin>>s[i];
        for(j=0;j<m;j++){
            if(s[i][j]=='A') a[0][j]+=w[i];
            if(s[i][j]=='C') a[1][j]+=w[i];
            if(s[i][j]=='G') a[2][j]+=w[i];
            if(s[i][j]=='T') a[3][j]+=w[i];
        }
    }
    for(i=0;i<n;i++) if(moze(i)) v.push_back(i);
    for(i=0;i<v.size();i++){
        if(jeste(v[i])) {cout<<v[i]+1<<endl; return 0;}
    }
    return 0;
}

Compilation message (stderr)

genetics.cpp: In function 'int main()':
genetics.cpp:51:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<v.size();i++){
             ~^~~~~~~~~

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