Submission #1063071

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063071		qwusha	Mutating DNA (IOI21_dna)	C++17	100 / 100	42 ms	6744 KiB

dna

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
typedef long double ld;
const ld eps = 1e-8;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const ll inf = 1e18;
const ll mod = 1e9 + 7;

#include "dna.h"

string a, b;
vector<int> at, ta, ac, ca, ct, tc;

void init(string na, string nb) {
    a = na;
    b = nb;
    int n = a.size();
    at.resize(n + 1);
    ta.resize(n + 1);
    ac.resize(n + 1);
    ca.resize(n + 1);
    ct.resize(n + 1);
    tc.resize(n + 1);
    for (int i = 0; i < n; i++) {
        ca[i + 1] = ca[i];
        ac[i + 1] = ac[i];
        at[i + 1] = at[i];
        ta[i + 1] = ta[i];
        ct[i + 1] = ct[i];
        tc[i + 1] = tc[i];
        if (a[i] == 'A' && b[i] == 'C') {
            ac[i + 1]++;
        }
        if (a[i] == 'C' && b[i] == 'A') {
            ca[i + 1]++;
        }
        if (a[i] == 'A' && b[i] == 'T') {
            at[i + 1]++;
        }
        if (a[i] == 'T' && b[i] == 'A') {
            ta[i + 1]++;
        }
        if (a[i] == 'C' && b[i] == 'T') {
            ct[i + 1]++;
        }
        if (a[i] == 'T' && b[i] == 'C') {
            tc[i + 1]++;
        }
    }
}

int get_distance(int x, int y) {
    int AC = ac[y + 1] - ac[x],
    CA = ca[y + 1] - ca[x],
    AT = at[y + 1] - at[x],
    TA = ta[y + 1] - ta[x],
    CT = ct[y + 1] - ct[x],
    TC = tc[y + 1] - tc[x];
    if (AT + AC != CA + TA)
        return -1;
    if (TA + TC != AT + CT)
        return -1;
    if (CA + CT != AC + TC)
        return -1;
    return min(CA, AC) + min(CT, TC) + min(AT, TA) + 2 * (max(CA, AC) - min(AC, CA));
}


/*
int main() {
    int n, q;
    cin >> n >> q;
    string na, nb;
    cin >> na >> nb;
    init(na, nb);
    for (int qw = 0; qw < q; qw++) {
        int x, y;
        cin >> x >> y;
        cout << get_distance(x, y) << '\n';
    }
}

*/

• Subtask 1: 21 / 21
• Subtask 2: 22 / 22
• Subtask 3: 13 / 13
• Subtask 4: 28 / 28
• Subtask 5: 16 / 16