Submission #441434

#	Time	Username	Problem	Language	Result	Execution time	Memory
441434		sam571128	Genetics (BOI18_genetics)	C++17	46 / 100	2064 ms	22016 KiB

genetics

#include <bits/stdc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 4105;

int id[N], cnt[N][4], sum = 0, ans[N];
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int get(char c){
    if(c=='A') return 0;
    else if(c=='T') return 1;
    else if(c=='C') return 2;
    else return 3;
}

signed main(){
    fastio
    fill(ans,ans+N,1);
    int n,m,k;
    cin >> n >> m >> k;
    vector<string> v;
    for(int i = 0;i < n;i++){
        string s;
        cin >> s;
        v.push_back(s);
    }


    //cout << "DONE!\n";
    for(int t = 0;t < 20;t++){
        //cout << t << '\n';
        sum = 0;
        for(int i = 0;i < n;i++){
            id[i] = rng()+i;
            //cout << i << " " << id[i] << "\n";
            sum += id[i];
        }

        for(int i = 0;i < m;i++){
            cnt[i][0] = cnt[i][1] = cnt[i][2] = cnt[i][3] = 0;
        }

        for(int i = 0;i < n;i++){
            for(int j = 0;j < m;j++){                
                cnt[j][get(v[i][j])] += id[i];
            }
        }

        for(int i = 0;i < n;i++){
            int res = 0;
            bool tmp = true;
            for(int j = 0;j < m;j++){
                res += (sum-cnt[j][get(v[i][j])]);
            }
            tmp = (res==(sum-id[i])*k);
            ans[i] &= tmp;
        }
        
    }

    for(int i = 0;i < n;i++){
        if(ans[i]){
            cout << i+1 << "\n";
            return 0;
        }
    }
}

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