Submission #625359

#	Time	Username	Problem	Language	Result	Execution time	Memory
625359		tabr	Mutating DNA (IOI21_dna)	C++17	100 / 100	46 ms	7412 KiB

dna

#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

int pref[100010][9];

void init(string a, string b) {
    int n = (int) a.size();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 9; j++) {
            pref[i + 1][j] = pref[i][j];
        }
        int x = (a[i] == 'A' ? 0 : (a[i] == 'C' ? 1 : 2));
        int y = (b[i] == 'A' ? 0 : (b[i] == 'C' ? 1 : 2));
        pref[i + 1][3 * x + y]++;
    }
}

int get_distance(int x, int y) {
    int ac = pref[y + 1][1] - pref[x][1];
    int at = pref[y + 1][2] - pref[x][2];
    int ca = pref[y + 1][3] - pref[x][3];
    int ct = pref[y + 1][5] - pref[x][5];
    int ta = pref[y + 1][6] - pref[x][6];
    int tc = pref[y + 1][7] - pref[x][7];
    int res = 0;
    int z = min(ac, ca);
    res += z;
    ac -= z;
    ca -= z;
    z = min(ct, tc);
    res += z;
    ct -= z;
    tc -= z;
    z = min(ta, at);
    res += z;
    ta -= z;
    at -= z;
    if (ac != ct || ct != ta || ta != ac || at != tc || tc != ca || ca != at) {
        return -1;
    }
    res += max({ac, at, ca, ct, ta, tc}) * 2;
    return res;
}

#ifdef tabr
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    init("ATACAT", "ACTATA");
    debug(get_distance(1, 3));
    return 0;
}
#endif

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