Submission #1189581

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189581		comxdddddd	Mutating DNA (IOI21_dna)	C++20	35 / 100	24 ms	7184 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;

const int MAX = 100000;

vector<int> paA(MAX + 1), paT(MAX + 1), paC(MAX + 1), pbA(MAX + 1), pbT(MAX + 1), pbC(MAX + 1);
vector<int> pAT(MAX + 1), pTA(MAX + 1), pAC(MAX + 1), pCA(MAX + 1), pTC(MAX + 1), pCT(MAX + 1);

void init(string a, string b)
{
    paA[0] = paT[0] = paC[0] = pbA[0] = pbT[0] = pbC[0] = pAT[0] = pTA[0] = pAC[0] = pCA[0] = pTC[0] = pCT[0] = 0;
    for (int i = 0; i < a.size(); i++)
    {
        paA[i + 1] = paA[i] + (a[i] == 'A');
        paT[i + 1] = paT[i] + (a[i] == 'T');
        paC[i + 1] = paC[i] + (a[i] == 'C');
        pbA[i + 1] = pbA[i] + (b[i] == 'A');
        pbT[i + 1] = pbT[i] + (b[i] == 'T');
        pbC[i + 1] = pbC[i] + (b[i] == 'C');
        pAT[i + 1] = pAT[i];
        pTA[i + 1] = pTA[i];
        pAC[i + 1] = pAC[i];
        pCA[i + 1] = pCA[i];
        pTC[i + 1] = pTC[i];
        pCT[i + 1] = pCT[i];
        if (a[i] == 'A' && b[i] == 'T')
            pAT[i + 1]++;
        else if (a[i] == 'T' && b[i] == 'A')
            pTA[i + 1]++;
        else if (a[i] == 'A' && b[i] == 'C')
            pAC[i + 1]++;
        else if (a[i] == 'C' && b[i] == 'A')
            pCA[i + 1]++;
        else if (a[i] == 'T' && b[i] == 'C')
            pTC[i + 1]++;
        else if (a[i] == 'C' && b[i] == 'T')
            pCT[i + 1]++;
    }
}

int get_distance(int x, int y)
{
    int caA = paA[y + 1] - paA[x];
    int caT = paT[y + 1] - paT[x];
    int caC = paC[y + 1] - paC[x];
    int cbA = pbA[y + 1] - pbA[x];
    int cbT = pbT[y + 1] - pbT[x];
    int cbC = pbC[y + 1] - pbC[x];
    if (caA != cbA || caT != cbT || caC != cbC)
        return -1;
    int AT = pAT[y + 1] - pAT[x];
    int TA = pTA[y + 1] - pTA[x];
    int AC = pAC[y + 1] - pAC[x];
    int CA = pCA[y + 1] - pCA[x];
    int TC = pTC[y + 1] - pTC[x];
    int CT = pCT[y + 1] - pCT[x];
    int d = min(AT, TA) + min(AC, CA) + min(TC, CT);
    return d;
}

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