Submission #1179021

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179021		walizamanee	Genetics (BOI18_genetics)	C++20	46 / 100	2094 ms	20280 KiB

genetics

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n , m , k , chek[4101][26] , ans , tim , one , two , nn , siz;    // abar koro ?
string a[4101];

vector<int> perm , ek , dui , tin;
int diff( int me , int her ) {
    int dif = 0;
    for( int z = 0; z < m; z++ ) {
        if( a[me][z] != a[her][z] ) dif++;
    }
    return dif;
}
void getans( int me ) {
    int hey = 0;

    for( int z = 0; z < n; z++ ) {
        if( perm[z] != me ) {
            hey = diff( me , perm[z] );
            if( hey != k ) {
                z = n;
            }
        }
        if( z == n - 1 ) ans = me;
    }
} 


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> k;
    ans = -1;
    for( int z = 0; z < n; z++ ) perm.push_back(z);

    random_device rd;
    mt19937 g(rd());
    shuffle(perm.begin(), perm.end(), g);
    for( int z = 0; z < n; z++ ) {
         cin >> a[z];
         for( int y = 0; y < m; y++ ) {
            chek[y][(int)(a[z][y] - 'A')]++;
         }
         ek.push_back(z);
    }
    siz = n;
    nn = n + 1;
    while( siz < nn ) { // nn mane aagertar siz
    nn = siz;
    for( int z = 0; z < tin.size(); z++ ) {
        for( int y = 0; y < m; y++ ) {
            chek[y][(int)(a[tin[z]][y] - 'A')]--;
        }
    }
    tin.clear();
    for( int z = 0; z < nn; z++ ) {
        one = 0;
        for( int y = 0; y < m; y++ ) {
            one += (nn - chek[y][(int)(a[ek[z]][y] - 'A')] );
        }
       // cout << one << " " << (k * (n - 1)) << " " << n << " " << k <<  "\n";
        if( one == (k * (nn - 1)) ) {
            dui.push_back(ek[z]);
        }
        else{
            tin.push_back(ek[z]);
        }
    }
    ek = dui;
    siz = ek.size();
    }
    for( int z = 0; z < (int)ek.size(); z++ ) {
        getans( ek[z] );
        if( ans != -1 ) z = n;
    }
    cout << ans + 1 << "\n"; 
    return 0;
}
 



 

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