Submission #984486

#	Time	Username	Problem	Language	Result	Execution time	Memory
984486		Ahmed57	Genetics (BOI18_genetics)	C++17	100 / 100	1821 ms	30456 KiB

genetics

#include <bits/stdc++.h>

using namespace std;
const int T = 30;
int nah[T][4101][4];
int sz[T];
bitset<4101>xd[T];
mt19937 rng;
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    rng.seed(time(0));
    int n,m,k;
    cin>>n>>m>>k;
    vector<string> v(n);
    for(int i = 0;i<n;i++)cin>>v[i];
    for(int it = 0;it<T;it++){
        for(int j = 0;j<n;j++){
            if(rng()%2){
                xd[it][j] = 1;
                sz[it]++;
                for(int e = 0;e<m;e++){
                    if(v[j][e]=='A')nah[it][e][0]++;
                    else if(v[j][e]=='C')nah[it][e][1]++;
                    else if(v[j][e]=='G')nah[it][e][2]++;
                    else nah[it][e][3]++;
                }
            }
        }
    }
    for(int i = 0;i<n;i++){
        bool bad = 0;
        for(int it = 0;it<T;it++){
            int lol = k*sz[it];
            if(xd[it][i]){
                lol-=k;
            }
            for(int e = 0;e<m;e++){
                if(v[i][e]=='A')lol-=nah[it][e][1]+nah[it][e][2]+nah[it][e][3];
                if(v[i][e]=='C')lol-=nah[it][e][0]+nah[it][e][2]+nah[it][e][3];
                if(v[i][e]=='G')lol-=nah[it][e][0]+nah[it][e][1]+nah[it][e][3];
                if(v[i][e]=='T')lol-=nah[it][e][0]+nah[it][e][1]+nah[it][e][2];
            }
            if(lol!=0){
                bad = 1;
                break;
            }
        }
        if(bad==0){
            cout<<i+1<<endl;
            return 0;
        }
    }
}

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