Submission #622368

#	Time	Username	Problem	Language	Result	Execution time	Memory
622368		no_namee	Genetics (BOI18_genetics)	C++14	100 / 100	1077 ms	35788 KiB

genetics

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ordered_multiset tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>
#define down '\n'
#define lli long long int
#define ulli unsigned long long int
#define ld long double
using namespace std;
using namespace __gnu_pbds;

const int maxn = 4150;
const int NUM_TEST = 4;
char ADN[] = {'A','C','G','T'};

char a[maxn][maxn];
gp_hash_table< char , lli > save[maxn];
lli n,m,k, sum;
lli val[maxn] , countt[maxn];

void rand_arr()
{
    sum = 0;
    for( int i = 1; i <= n; i ++ )
    {
        val[i] = ( rand()%12345678 + 123 );
        sum += val[i];
    }
    for( int i = 1; i <= m; i ++ )
    {
        for( auto & j : save[i] ) j.second = 0;
    }
    for( int i = 1; i <= n; i ++ )
    {
        for( int j = 1; j <= m; j ++ )
        {
            save[j][ a[i][j] ] +=  val[i];
        }
    }
}
void process( int need )
{
    rand_arr();
    for( int i = 1; i <= n; i ++ )
    {
        if( countt[i] < need ) continue;
        lli summm = 0;
        for( int j = 1 ; j <= m; j ++ )
        {
            for( int k = 0 ; k < 4;k ++ )
            {
                if( a[i][j] != ADN[k] ) summm += save[j][ ADN[k] ];
            }
        }
        if( summm ==  ( (sum - val[i] )*k ) ) countt[i]++;
    }
}
void read()
{
	cin >> n >> m >> k;
	for( int i = 1; i <= n; i ++ )
    {
        for( int j = 1; j <= m; j ++ ) cin >> a[i][j];
    }
}
void solve()
{
    for( int i = 0 ; i < NUM_TEST; i ++ ) process(i);
    for( int i = 1; i <=  n; i ++ )
    {
        if( countt[i] == NUM_TEST )
        {
            cout << i;
            exit(0);
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    srand( time(nullptr) );
    read();
    solve();
    return 0;
}

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