Submission #830628

#	Time	Username	Problem	Language	Result	Execution time	Memory
830628		Johann	Genetics (BOI18_genetics)	C++14	0 / 100	31 ms	23956 KiB

genetics

#include<bits/stdc++.h>
using namespace std;

#define vi vector<int>
#define vvi vector<vi>
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()

int MAP[4] = { 'A', 'C', 'G', 'T' };
struct genom {
    int idx = -1;
    vi gen;
    void readGen(int i) {
        idx = i;
        string s;
        cin >> s;
        int M = sz(s);
        gen.resize(M);
        for (int j = 0; j < M; ++j) {
            if (s[j] == 'A') gen[j] = 0;
            else if (s[j] == 'C') gen[j] = 1;
            else if (s[j] == 'G') gen[j] = 2;
            else gen[j] = 3;
        }
    }
    void print() {
        for (int i : gen) cout << (char) MAP[i];
        cout << "\n";
    }
};

int compare(genom & g1, genom & g2) {
    int diff = 0;
    for (int i = 0; i < sz(g1.gen); ++i) {
        diff += (int) (g1.gen[i] != g2.gen[i]);
    }
    return diff;
}

void ReducePairs(vector<genom> & base, vector<genom> & raus, int K) {
    vector<genom> candidates;
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    shuffle(all(base), rng);
    int c = sz(candidates), r = sz(raus);
    while (sz(base) > 1) {
        int l1 = sz(base) - 1;
        int l2 = l1 - 1;
        if (compare(base[l1], base[l2]) == K) {
            candidates.emplace_back();
            candidates.emplace_back();
            swap(base[l1], candidates[c++]);
            swap(base[l2], candidates[c++]);
        } else {
            raus.emplace_back();
            raus.emplace_back();
            swap(raus[r++], base[l1]);
            swap(raus[r++], base[l2]);
        }
        base.pop_back();
        base.pop_back();
    }
    if (sz(base) == 1) {
        candidates.emplace_back();
        swap(base[0], candidates[c++]);
        base.pop_back();
    }
    swap(base, candidates);
}

void ReduceCount(vector<genom> & base, vector<genom> & raus, int K) {
    vector<genom> candidates;
    int c = 0, r = sz(raus);
    int N = sz(base);
    int M = sz(base[0].gen);
    vvi cnts(M, vi(4, 0));
    for (int j = 0; j < N; ++j) {
        for (int i = 0; i < M; ++i) ++cnts[i][base[j].gen[i]];
    }
    int ziel = M * N - (N - 1) * K;
    for (int j = N-1; j >= 0; --j) {
        int sum = 0;
        for (int i = 0; i < M; ++i) sum += cnts[i][base[j].gen[i]];
        if (sum == ziel) {
            candidates.emplace_back();
            swap(base[j], candidates[c++]);
        } else {
            raus.emplace_back();
            swap(base[j], raus[r++]);
        }
    }
    swap(base, candidates);
}

void ReduceRest(vector<genom> & base, vector<genom> & raus, int K) {
    vector<genom> candidates;
    int c = 0, r = sz(raus);
    for (int j = sz(base)-1; j >= 0; --j) {
        bool poss = true;
        for (genom g : raus) {
            if (compare(base[j], g) != K) { poss = false; break; }
        }
        if (poss) {
            for (int k = 0; k < j; ++k) {
                if (compare(base[k], base[j]) != K) { poss = false; break; }
            }
        }
        if (poss) {
            candidates.emplace_back();
            swap(base[j], candidates[c++]);
        } else {
            raus.emplace_back();
            swap(base[j], raus[r++]);
        }
        base.pop_back();
    }
    swap(base, candidates);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);


    int N, M, K;
    scanf("%d %d %d", & N, & M, & K);
    vector<genom> gens(N);
    for (int i = 0; i < N; ++i) {
        gens[i].readGen(i);
    }
    cout << "read Input completed\n";

    vector<genom> raus;
    ReduceCount(gens, raus, K);
    cout << "Count\n";

    // for (genom g : gens) g.print();
    int altsize = sz(gens) + 1;
    while (altsize > sz(gens)) {
        altsize = sz(gens);
        ReducePairs(gens, raus, K);
    }
    cout << "Pairs\n";

    // for (genom g : gens) g.print();

    ReduceRest(gens, raus, K);
    cout << "Rest\n";

    for (genom g : gens) cout << g.idx+1 << endl;

}

Compilation message (stderr)

genetics.cpp: In function 'int main()':
genetics.cpp:126:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |     scanf("%d %d %d", & N, & M, & K);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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