Submission #1000051

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000051		codefox	Mutating DNA (IOI21_dna)	C++17	100 / 100	30 ms	6168 KiB

dna

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

using namespace std;

vector<int> AC;
vector<int> AT;
vector<int> CA;
vector<int> CT;
vector<int> TA;
vector<int> TC;

void init(string a, string b)
{
    int n = a.size();
    AC.assign(n+1, 0);
    AT.assign(n+1, 0);
    CA.assign(n+1, 0);
    CT.assign(n+1, 0);
    TA.assign(n+1, 0);
    TC.assign(n+1, 0);
    for (int i = 0; i < n; i++)
    {
        AC[i+1] = AC[i];
        AT[i+1] = AT[i];
        CA[i+1] = CA[i];
        CT[i+1] = CT[i];
        TA[i+1] = TA[i];
        TC[i+1] = TC[i];
        if (a[i]=='A')
        {
            if (b[i]=='C') AC[i+1]++;
            if (b[i]=='T') AT[i+1]++;
        }
        if (a[i]=='C')
        {
            if (b[i]=='A') CA[i+1]++;
            if (b[i]=='T') CT[i+1]++;
        }
        if (a[i]=='T')
        {
            if (b[i]=='A') TA[i+1]++;
            if (b[i]=='C') TC[i+1]++;
        }
    }
}


int get_distance(int y, int x)
{
    int sol = 0;
    int ac = AC[x+1]-AC[y];
    int at = AT[x+1]-AT[y];
    int ca = CA[x+1]-CA[y];
    int ct = CT[x+1]-CT[y];
    int ta = TA[x+1]-TA[y];
    int tc = TC[x+1]-TC[y];
    if (ac+at != ta+ca) return -1;
    if (ca+ct != tc+ac) return -1;
    if (ta+tc != at+ct) return -1;
    sol += min(ac, ca) +min(at, ta) + min(ct, tc);
    sol += (max(ac, ca) - min(ac, ca))*2;
    return sol;
}

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