Submission #1274678

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274678		veham	Genetics (BOI18_genetics)	C++20	100 / 100	625 ms	229500 KiB

genetics

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef string str;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef set<int> si;
typedef vector<vi> vvi;
typedef vector<str> vs;

int operator*(vi &a, vi &b){
    int ans = 0;
    for(int i = 0;i < a.size();i++) ans += a[i]*b[i];
    return ans;
}

vi operator+(vi &a, vi &b){
    vi v(a.size());
    for(int i = 0;i < a.size();i++) v[i] = a[i] + b[i];
    return v;
}

vi operator-(vi &a, vi &b){
    vi v(a.size());
    for(int i = 0;i < a.size();i++) v[i] = a[i] - b[i];
    return v;
}

int prob(int N, int M, int K, vs &D){
    vvi V(N,vi(3*M));
    for(int i = 0;i < N;i++){
        for(int j = 0;j < M;j++){
            V[i][3*j] = (D[i][j] == 'A' ? 1 : -1);
            V[i][3*j+1] = (D[i][j] == 'T' ? 1 : -1);
            V[i][3*j+2] = (D[i][j] == 'C' ? 1 : -1);
            if(D[i][j] == 'G') V[i][3*j] = V[i][3*j+1] = V[i][3*j+2] = 1;
        }
    }
    int num_left = N, num_curr = 0, num_curr2;
    vi sum, sum2;
    vb left(N,1), curr=left;
    int K2 = 3*M - 4*K;
    for(;num_left > 1;num_curr = 0){
        sum.assign(3*M,0);
        for(int i = 0;i < N;i++){
            curr[i] = rand()%2;
            if(!curr[i]) continue;
            sum = sum + V[i];
            num_curr++;
        }
        for(int i = 0;i < N;i++){
            if(!left[i]) continue;
            num_curr2 = num_curr - curr[i];
            sum2 = curr[i] ? sum - V[i] : sum;
            if(V[i] * sum2 == K2 * num_curr2) continue;
            left[i] = 0;
            num_left--;
        }
    }
    return find(left.begin(),left.end(),true) - left.begin();
}

int main(){
    int N,M,K;
    cin >> N >> M >> K;
    vs D(N);
    for(int i = 0;i < N;i++) cin >> D[i];
    cout << (prob(N,M,K,D) + 1);
    return 0;
}

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