Submission #1088312

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088312		vjudge1	Mutating DNA (IOI21_dna)	C++17	100 / 100	35 ms	8632 KiB

dna

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

using namespace std;

const int maxn = 100005;

int n;
int prefa1[maxn], prefa2[maxn];
int prefc1[maxn], prefc2[maxn];
int preft1[maxn], preft2[maxn];

int prefac[maxn], prefat[maxn], prefca[maxn], prefct[maxn], prefta[maxn], preftc[maxn];

void init(string a, string b)
{
    n = a.size();
    a = "#" + a;
    b = "#" + b;

    for (int i = 1; i <= n; ++i)
    {
        prefa1[i] = prefa1[i - 1];
        prefa2[i] = prefa2[i - 1];
        prefc1[i] = prefc1[i - 1];
        prefc2[i] = prefc2[i - 1];
        preft1[i] = preft1[i - 1];
        preft2[i] = preft2[i - 1];

        prefac[i] = prefac[i - 1];
        prefat[i] = prefat[i - 1];
        prefca[i] = prefca[i - 1];
        prefct[i] = prefct[i - 1];
        prefta[i] = prefta[i - 1];
        preftc[i] = preftc[i - 1];

        if (a[i] == 'A') ++prefa1[i];
        else if (a[i] == 'C') ++prefc1[i];
        else if (a[i] == 'T') ++preft1[i];

        if (b[i] == 'A') ++prefa2[i];
        else if (b[i] == 'C') ++prefc2[i];
        else if (b[i] == 'T') ++preft2[i];

        if (a[i] == 'A' && b[i] == 'C') ++prefac[i];
        else if (a[i] == 'A' && b[i] == 'T') ++prefat[i];
        else if (a[i] == 'C' && b[i] == 'A') ++prefca[i];
        else if (a[i] == 'C' && b[i] == 'T') ++prefct[i];
        else if (a[i] == 'T' && b[i] == 'A') ++prefta[i];
        else if (a[i] == 'T' && b[i] == 'C') ++preftc[i];
    }
}

int get_distance(int x, int y)
{
    ++x;
    ++y;

    if (prefa1[y] - prefa1[x - 1] != prefa2[y] - prefa2[x - 1]) return -1;
    if (prefc1[y] - prefc1[x - 1] != prefc2[y] - prefc2[x - 1]) return -1;
    if (preft1[y] - preft1[x - 1] != preft2[y] - preft2[x - 1]) return -1;

    int ans = 0;

    ans += min(prefac[y] - prefac[x - 1], prefca[y] - prefca[x - 1]);
    ans += max(prefat[y] - prefat[x - 1], prefta[y] - prefta[x - 1]);
    ans += max(prefct[y] - prefct[x - 1], preftc[y] - preftc[x - 1]);

    return ans;
}

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