Submission #1178992

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178992		walizamanee	Genetics (BOI18_genetics)	C++20	46 / 100	2093 ms	20236 KiB

genetics

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

vector<int> perm;
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];
      //  cout << k << "\n";
        for( int y = 0; y < m; y++ ) {
            chek[y][(int)(a[z][y] - 'A')]++;
          //  if( k == 2 ) cout << "here" << z << y << "\n";
        }
    }
    
    for( int z = 0; z < n; z++ ) {
        one = 0;
        for( int y = 0; y < m; y++ ) {
            one += (n - chek[y][(int)(a[z][y] - 'A')] );
        }
       // cout << one << " " << (k * (n - 1)) << " " << n << " " << k <<  "\n";
        if( one == (k * (n - 1)) ) {
            getans( z );
           // cout << z << "\n";
            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