Submission #1215668

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215668		gortomi	Mutating DNA (IOI21_dna)	C++20	100 / 100	26 ms	9232 KiB

dna

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

const int maxn = 1e5 + 5;
int p1[maxn][3];
int p2[maxn][3];
int p3[maxn][3][3];
int s1[maxn];
int s2[maxn];

void init(string a, string b) {
    memset(p1, 0, sizeof(p1));
    memset(p2, 0, sizeof(p2));
    memset(p3, 0, sizeof(p3));
    for (int i = 0; i < a.size(); i++) {
        if (a[i] == 'A')
            s1[i] = 0;
        else if (a[i] == 'C')
            s1[i] = 1;
        else
            s1[i] = 2;

        if (b[i] == 'A')
            s2[i] = 0;
        else if (b[i] == 'C')
            s2[i] = 1;
        else
            s2[i] = 2;
    }

    p1[0][s1[0]]++;
    p2[0][s2[0]]++;
    p3[0][s1[0]][s2[0]]++;
    for (int i = 1; i < a.size(); i++) {
        for (int t1 = 0; t1 <= 2; t1++) {
            for (int t2 = 0; t2 <= 2; t2++) {
                p3[i][t1][t2] = p3[i - 1][t1][t2];
            }
            p1[i][t1] = p1[i - 1][t1];
            p2[i][t1] = p2[i - 1][t1];
        }

        p3[i][s1[i]][s2[i]]++;
        p1[i][s1[i]]++;
        p2[i][s2[i]]++;
    }
}

int c[3][3];

int get_distance(int x, int y) {
    if (x == 0) {
        if (p1[y][0] != p2[y][0] || p1[y][1] != p2[y][1] || p1[y][2] != p2[y][2]) {
            return -1;
        }
    } else {
        if (p1[y][0] - p1[x - 1][0] != p2[y][0] - p2[x - 1][0] ||
            p1[y][1] - p1[x - 1][1] != p2[y][1] - p2[x - 1][1] ||
            p1[y][2] - p1[x - 1][2] != p2[y][2] - p2[x - 1][2]) {
            return -1;
        }
    }

    for (int i = 0; i <= 2; i++) {
        for (int j = 0; j <= 2; j++) {
            if (x == 0)
                c[i][j] = p3[y][i][j];
            else
                c[i][j] = p3[y][i][j] - p3[x - 1][i][j];
        }
    }

    int ans = 0;
    int all = y - x + 1;
    all -= c[0][0];
    all -= c[1][1];
    all -= c[2][2];
    int h = min(c[0][1], c[1][0]);
    ans += h;
    all -=2* h;
    h = min(c[0][2], c[2][0]);
    ans += h;
    all -=2* h;
    h = min(c[1][2], c[2][1]);
    ans += h;
    all -=2* h;
    ans += (all / 3) * 2;

    return ans;
}

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