Submission #888355

#	Time	Username	Problem	Language	Result	Execution time	Memory
888355		1075508020060209tc	Genetics (BOI18_genetics)	C++14	100 / 100	1558 ms	346280 KiB

genetics

#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
//#define int long long
//const int mod=998244353;
unsigned long long seed=1234;
unsigned long long rnd(){
seed^=seed<<13;
seed^=seed>>7;
seed^=seed>>6;
return seed;
}

int n;int m;int K;
int gr[4105][4105];
int ps[4][4105][4105];
int mby[4105];
void init(){
cin>>n>>m>>K;
string s;
for(int i=1;i<=n;i++){
    cin>>s;
    s="*"+s;
    for(int j=1;j<=m;j++){
        if(s[j]=='A'){
            gr[i][j]=0;
        }
        if(s[j]=='C'){
            gr[i][j]=1;
        }
        if(s[j]=='G'){
            gr[i][j]=2;
        }
        if(s[j]=='T'){
            gr[i][j]=3;
        }
    }
}
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        ps[gr[i][j]][i][j]++;
        for(int k=0;k<4;k++){
            ps[k][i][j]+=ps[k][i-1][j];
        }
    }
}

}

int ok(int id){
int dif=0;
for(int i=1;i<=m;i++){
    dif+=n-ps[gr[id][i]][n][i];
}
if(dif!=K*(n-1)){return 0;}
for(int ttt=1;ttt<=30;ttt++){
    int pl=1+rnd()%n;
    dif=0;
    for(int i=1;i<=m;i++){
        dif+=pl-ps[gr[id][i]][pl][i];
    }
    if(dif!=K*pl-((pl>=id)*K) ){return 0;}
    dif=0;
    pl--;
    for(int i=1;i<=m;i++){
        dif+=(n-pl)-(ps[gr[id][i]][n][i]-ps[gr[id][i]][pl][i]);
    }
    if(dif!=K*(n-pl)-((pl<id)*K) ){return 0;}
}
for(int ttt=1;ttt<=70;ttt++){
    int pl=1+rnd()%n;
    if(pl==id){continue;}
    dif=0;
    for(int i=1;i<=m;i++){
        if(gr[id][i]!=gr[pl][i]){dif++;}
        if(dif>K){break;}
    }
    if(dif!=K){
        mby[pl]=-1;
        return 0;
    }
}
return 1;
}

int fchk(int id){

for(int pl=1;pl<=n;pl++){
    if(pl==id){continue;}
    int dif=0;
    for(int i=1;i<=m;i++){
        if(gr[id][i]!=gr[pl][i]){dif++;}
    }
    if(dif!=K){return 0;}
}
return 1;
}

signed main(){
init();
for(int i=1;i<=n;i++){
    if(mby[i]==-1){continue;}
    mby[i]=ok(i);
    /*if(mby[i]){
        cout<<i;return 0;
    }*/
}

int cnt=0;
for(int i=1;i<=n;i++){
    if(mby[i]==1){cnt++;}
}
assert(cnt<=500);
for(int i=1;i<=n;i++){
    if(mby[i]==1&&fchk(i)){
        cout<<i;return 0;
    }

}


}

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