Submission #437062

#	Time	Username	Problem	Language	Result	Execution time	Memory
437062		_martynas	Mutating DNA (IOI21_dna)	C++17	100 / 100	66 ms	9220 KiB

dna

#include "dna.h"

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5+5;

int TotalA[MAX_N][3], TotalB[MAX_N][3];
int Rep[MAX_N][3][3];
int A[MAX_N];
int B[MAX_N];
int n;

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

    for(int i = 0; i < n; i++) {
        switch(a[i]) {
        case 'A':
            A[i] = 0;
            break;
        case 'C':
            A[i] = 1;
            break;
        case 'T':
            A[i] = 2;
            break;
        }

        switch(b[i]) {
        case 'A':
            B[i] = 0;
            break;
        case 'C':
            B[i] = 1;
            break;
        case 'T':
            B[i] = 2;
            break;
        }
    }

    for(int i = 0; i < n; i++) {
        for(int k = 0; k < 3; k++) {
            if(i) {
                TotalA[i][k] = TotalA[i - 1][k];
                TotalB[i][k] = TotalB[i - 1][k];
            }
            TotalA[i][k] += (A[i] == k);
            TotalB[i][k] += (B[i] == k);
        }
        if(i) {
            for(int ii = 0; ii < 3; ii++) {
                for(int jj = 0; jj < 3; jj++) {
                    Rep[i][ii][jj] = Rep[i-1][ii][jj];
                }
            }
        }
        if(A[i] != B[i]) {
            Rep[i][A[i]][B[i]]++;
        }
    }
}

int get_distance(int x, int y)
{
    int totA[3], totB[3];
    for(int k = 0; k < 3; k++) {
        totA[k] = TotalA[y][k] - (x ? TotalA[x-1][k] : 0);
        totB[k] = TotalB[y][k] - (x ? TotalB[x-1][k] : 0);
        if(totA[k] != totB[k]) {
            return -1;
        }
    }

    int sum = 0;
    int dist = 0;
    int R[3][3] = { 0 };

    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 3; j++) {
            R[i][j] = Rep[y][i][j] - (x ? Rep[x-1][i][j] : 0);
        }
    }

    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 3; j++) {
            sum += R[i][j];
            if(i <= j)
                continue;
            dist += min(R[i][j], R[j][i]);
            sum -= 2 * min(R[i][j], R[j][i]);
        }
    }

    return dist + sum / 3 * 2;
}

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