Submission #598757

#	Time	Username	Problem	Language	Result	Execution time	Memory
598757		urosk	Genetics (BOI18_genetics)	C++14	100 / 100	779 ms	149044 KiB

genetics

#define here cerr<<"===========================================\n"
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll l,ll r){
    return uniform_int_distribution<ll>(l,r)(rng);
}
#define maxn 4105
ll n,m,k;
ll a[maxn][maxn];
ll cnt[maxn][5][2];
bool ok[maxn];
ll cntok;
ll siz[maxn];
ll siz2[maxn];
ll id[maxn];
int main(){
	daj_mi_malo_vremena
    cin >> n >> m >> k;
    for(ll i = 1;i<=n;i++){
        ok[i] = 1;
        string s; cin >> s;
        for(ll j = 1;j<=m;j++){
            if(s[j-1]=='A') a[i][j] = 1;
            if(s[j-1]=='G') a[i][j] = 2;
            if(s[j-1]=='C') a[i][j] = 3;
            if(s[j-1]=='T') a[i][j] = 4;
        }
    }
    cntok = n;
    while(cntok>1){
        for(ll i = 1;i<=m;i++) for(ll j = 1;j<=4;j++) cnt[i][j][0] = cnt[i][j][1] = 0;
        siz[0] = siz[1] = 0;
        for(ll i = 1;i<=n;i++){
            id[i] = rnd(0,1);
            siz[id[i]]++;
            for(ll j = 1;j<=m;j++) cnt[j][a[i][j]][id[i]]++;
        }
        for(ll i = 1;i<=n;i++){
            if(!ok[i]) continue;
            siz2[0] = siz2[1] = 0;
            for(ll j = 1;j<=m;j++){
                for(ll e = 0;e<=1;e++) siz2[e] += siz[e] - cnt[j][a[i][j]][e];
            }
            siz[id[i]]--;
            if(siz[1]*k!=siz2[1]){
                ok[i] = 0;
                cntok--;
            }else if(siz[0]*k!=siz2[0]){
                ok[i] = 0;
                cntok--;
            }
            siz[id[i]]++;
        }
    }
    ll ans = -1;
    for(ll i = 1;i<=n;i++) if(ok[i]) ans = i;
    cout<<ans<<endl;
	return 0;
}
/*
4 3 1
ACC
CCA
ACA
AAA

4 4 3
CATT
CAAA
ATGA
TCTA
*/

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