Submission #1034395

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034395		Boas	Mutating DNA (IOI21_dna)	C++17	100 / 100	30 ms	6912 KiB

dna

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

#define loop(x, i) for (int i = 0; i < x; i++)
#define pb push_back
#define ALL(x) begin(x), end(x)

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;

vi sumAC, sumAT, sumCA, sumCT, sumTA, sumTC;

void init(string a, string b)
{
    int n = a.size();
    sumAC = sumAT = sumCA = sumCT = sumTA = sumTC = {0};
    loop(n, i)
    {
        sumAC.pb(sumAC.back());
        sumAT.pb(sumAT.back());
        sumCA.pb(sumCA.back());
        sumCT.pb(sumCT.back());
        sumTA.pb(sumTA.back());
        sumTC.pb(sumTC.back());
        if (a[i] == b[i])
            continue;
        if (a[i] == 'A')
        {
            if (b[i] == 'C')
                sumAC.back()++;
            else
                sumAT.back()++;
        }
        else if (a[i] == 'C')
        {
            if (b[i] == 'A')
                sumCA.back()++;
            else
                sumCT.back()++;
        }
        else
        {
            if (b[i] == 'A')
                sumTA.back()++;
            else
                sumTC.back()++;
        }
    }
}

int get_distance(int i, int j)
{
    int AC = sumAC[j + 1] - sumAC[i];
    int AT = sumAT[j + 1] - sumAT[i];
    int CA = sumCA[j + 1] - sumCA[i];
    int TA = sumTA[j + 1] - sumTA[i];
    int CT = sumCT[j + 1] - sumCT[i];
    int TC = sumTC[j + 1] - sumTC[i];
    if (AC + AT != CA + TA)
        return -1;
    if (CA + CT != AC + TC)
        return -1;
    if (TA + TC != AT + CT)
        return -1;
    int res = 0;
    int ac = min(AC, CA);
    res += ac;
    AC -= ac;
    CA -= ac;
    int at = min(AT, TA);
    res += at;
    AT -= at;
    TA -= at;
    int ct = min(CT, TC);
    res += ct;
    CT -= ct;
    TC -= ct;
    return res + AC + AT + CA + TA;
}

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