Submission #1010419

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010419		induwara16	Mutating DNA (IOI21_dna)	C++17	0 / 100	26 ms	9688 KiB

dna

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

typedef string str;
typedef vector<int> vi;

str a, b;
vi ac, at, ca, ct, ta, tc, as1, cs1, ts1, as2, cs2, ts2;

void init(str a1, str b1)
{
    a = a1;
    b = b1;

    int n = a.length();

    ac = vi(n);
    at = vi(n);
    ca = vi(n);
    at = vi(n);
    ta = vi(n);
    tc = vi(n);

    for (int i = 0; i < n; i++)
    {
        switch (b[i])
        {
        case 'A':
            as2[i] = i == 0 ? 1 : as2[i - 1] + 1;
            cs2[i] = i == 0 ? 0 : cs2[i - 1];
            ts2[i] = i == 0 ? 0 : ts2[i - 1];
            break;
        case 'C':
            as2[i] = i == 0 ? 0 : as2[i - 1];
            cs2[i] = i == 0 ? 1 : cs2[i - 1] + 1;
            ts2[i] = i == 0 ? 0 : ts2[i - 1];
            break;
        case 'T':
            as2[i] = i == 0 ? 0 : as2[i - 1];
            cs2[i] = i == 0 ? 0 : cs2[i - 1];
            ts2[i] = i == 0 ? 1 : ts2[i - 1] + 1;
            break;
        }
        switch (a[i])
        {
        case 'A':
            as1[i] = i == 0 ? 1 : as1[i - 1] + 1;
            cs1[i] = i == 0 ? 0 : cs1[i - 1];
            ts1[i] = i == 0 ? 0 : ts1[i - 1];
            if (b[i] == 'C')
                ac[i] = i == 0 ? 1 : ac[i - 1] + 1;
            else
                ac[i] = i == 0 ? 0 : ac[i - 1];
            if (b[i] == 'T')
                at[i] = i == 0 ? 1 : at[i - 1] + 1;
            else
                at[i] = i == 0 ? 0 : at[i - 1];
            break;
        case 'C':
            as1[i] = i == 0 ? 0 : as1[i - 1];
            cs1[i] = i == 0 ? 1 : cs1[i - 1] + 1;
            ts1[i] = i == 0 ? 0 : ts1[i - 1];
            if (b[i] == 'A')
                ca[i] = i == 0 ? 1 : ca[i - 1] + 1;
            else
                ca[i] = i == 0 ? 0 : ca[i - 1];
            if (b[i] == 'T')
                ct[i] = i == 0 ? 1 : ct[i - 1] + 1;
            else
                ct[i] = i == 0 ? 0 : ct[i - 1];
            break;
        case 'T':
            as1[i] = i == 0 ? 0 : as1[i - 1];
            cs1[i] = i == 0 ? 0 : cs1[i - 1];
            ts1[i] = i == 0 ? 1 : ts1[i - 1] + 1;
            if (b[i] == 'C')
                tc[i] = i == 0 ? 1 : tc[i - 1] + 1;
            else
                tc[i] = i == 0 ? 0 : tc[i - 1];
            if (b[i] == 'A')
                ta[i] = i == 0 ? 1 : ta[i - 1] + 1;
            else
                ta[i] = i == 0 ? 0 : ta[i - 1];
            break;
        }
    }
}

int get_distance(int x, int y)
{
    if (
        (as1[y] - (x == 0 ? 0 : as1[x - 1])) != (as2[y] - (x == 0 ? 0 : as2[x - 1])) ||
        (cs1[y] - (x == 0 ? 0 : cs1[x - 1])) != (cs2[y] - (x == 0 ? 0 : cs2[x - 1])) ||
        (ts1[y] - (x == 0 ? 0 : ts1[x - 1])) != (ts2[y] - (x == 0 ? 0 : ts2[x - 1])))
        return -1;

    int cntAC = ac[y] - (x == 0 ? 0 : ac[x - 1]);
    int cntAT = at[y] - (x == 0 ? 0 : at[x - 1]);
    int cntCA = ca[y] - (x == 0 ? 0 : ca[x - 1]);
    int cntCT = ct[y] - (x == 0 ? 0 : ct[x - 1]);
    int cntTA = ta[y] - (x == 0 ? 0 : ta[x - 1]);
    int cntTC = tc[y] - (x == 0 ? 0 : tc[x - 1]);

    int c = 0, m = cntAC + cntCA + cntAT + cntTA + cntTC + cntTC;

    m -= min(cntAC, cntCA) * 2;
    c += min(cntAC, cntCA);

    m -= min(cntAT, cntTA) * 2;
    c += min(cntAT, cntTA);

    m -= min(cntTC, cntCT) * 2;
    c += min(cntTA, cntCT);

    return m / 3 * 2 + c;
}

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