Submission #502444

#	Time	Username	Problem	Language	Result	Execution time	Memory
502444		jjj	Mutating DNA (IOI21_dna)	C++17	100 / 100	51 ms	10100 KiB

dna

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

using namespace std;

int p1[MAXN][5], p2[MAXN][5], ac[MAXN], ca[MAXN], att[MAXN], ta[MAXN], ct[MAXN], tc[MAXN];

void init(std::string a, std::string b)
{
    int n = a.size();

    for(int i = 0; i < n; i++)
    {
        p1[i + 1][0] = p1[i][0];
        p1[i + 1][1] = p1[i][1];
        p1[i + 1][2] = p1[i][2];
        p2[i + 1][0] = p2[i][0];
        p2[i + 1][1] = p2[i][1];
        p2[i + 1][2] = p2[i][2];

        if(a[i] == 'A') p1[i + 1][0]++;
        if(a[i] == 'T') p1[i + 1][1]++;
        if(a[i] == 'C') p1[i + 1][2]++;

        if(b[i] == 'A') p2[i + 1][0]++;
        if(b[i] == 'T') p2[i + 1][1]++;
        if(b[i] == 'C') p2[i + 1][2]++;

        ac[i + 1] = ac[i];
        ca[i + 1] = ca[i];
        att[i + 1] = att[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') att[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)
{
    x++; y++;


    if(p1[y][0] - p1[x - 1][0] != p2[y][0] - p2[x - 1][0] || p1[y][1] - p1[x - 1][1] != p2[y][1] - p2[x - 1][1] || p1[y][2] - p1[x - 1][2] != p2[y][2] - p2[x - 1][2])
        return -1;

    int d = 0;

    d += abs(ac[y] - ac[x - 1] - ca[y] + ca[x - 1]) + abs(att[y] - att[x - 1] - ta[y] + ta[x - 1]) + abs(ct[y] - ct[x - 1] - tc[y] + tc[x - 1]);

    d /= 3;
    d *= 2;

    d += min(abs(ac[y] - ac[x - 1]), abs(ca[y] - ca[x - 1])) + min(abs(att[y] - att[x - 1]), abs(ta[y] - ta[x - 1])) + min(abs(ct[y] - ct[x - 1]), abs(tc[y] - tc[x - 1]));

	return d;
}

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