Submission #439309

#	Time	Username	Problem	Language	Result	Execution time	Memory
439309		4fecta	Mutating DNA (IOI21_dna)	C++17	100 / 100	53 ms	4872 KiB

dna

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pii pair<int, int>
#define f first
#define s second
#define boost() cin.tie(0), cin.sync_with_stdio(0)

const int MN = 100005;

int n, ac[MN], ca[MN], ct[MN], tc[MN], ta[MN], at[MN];

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

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

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