Submission #1003415

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003415		andrei_iorgulescu	Mutating DNA (IOI21_dna)	C++17	100 / 100	31 ms	8692 KiB

dna

#include <bits/stdc++.h>
#include "dna.h"

using namespace std;

int n;
int ab[100005],ba[100005],ac[100005],ca[100005],bc[100005],cb[100005];
int spa[3][100005],spb[3][100005];

void init(string a, string b)
{
    n = a.size();
    a = ' ' + a;
    b = ' ' + b;
    for (int i = 1; i <= n; i++)
    {
        if (a[i] == 'T')
            a[i] = 'b';
        if (b[i] == 'T')
            b[i] = 'b';
        if (a[i] == 'A')
            a[i] = 'a';
        if (b[i] == 'A')
            b[i] = 'a';
        if (a[i] == 'C')
            a[i] = 'c';
        if (b[i] == 'C')
            b[i] = 'c';
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < 3; j++)
            spa[j][i] = spa[j][i - 1],spb[j][i] = spb[j][i - 1];
        spa[a[i] - 'a'][i]++;
        spb[b[i] - 'a'][i]++;
        ab[i] = ab[i - 1];
        ba[i] = ba[i - 1];
        ac[i] = ac[i - 1];
        ca[i] = ca[i - 1];
        bc[i] = bc[i - 1];
        cb[i] = cb[i - 1];
        if (a[i] == 'a' and b[i] == 'b')
            ab[i]++;
        if (a[i] == 'b' and b[i] == 'a')
            ba[i]++;
        if (a[i] == 'a' and b[i] == 'c')
            ac[i]++;
        if (a[i] == 'c' and b[i] == 'a')
            ca[i]++;
        if (a[i] == 'b' and b[i] == 'c')
            bc[i]++;
        if (a[i] == 'c' and b[i] == 'b')
            cb[i]++;
    }
}

int get_distance(int x,int y)
{
    x++;
    y++;
    for (int j = 0; j < 3; j++)
        if (spa[j][y] - spa[j][x - 1] != spb[j][y] - spb[j][x - 1])
            return -1;
    int ans = min(ab[y] - ab[x - 1],ba[y] - ba[x - 1]) + min(ac[y] - ac[x - 1],ca[y] - ca[x - 1]) + min(bc[y] - bc[x - 1],cb[y] - cb[x - 1]);
    ans += 2 * (max(ab[y] - ab[x - 1],ba[y] - ba[x - 1]) - min(ab[y] - ab[x - 1],ba[y] - ba[x - 1]));
    return ans;
}

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