Submission #1215667

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215667		horka	DNA 돌연변이 (IOI21_dna)	C++20	56 / 100	22 ms	8356 KiB

dna

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

using namespace std;

const int MAXN = 1e5+5;

int n;

int qca[MAXN][3], qcb[MAXN][3];
int df[MAXN][3][3];

int id(char c) {
    if (c == 'A') return 0;
    else if (c == 'T') return 1;
    else return 2;
}

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

    a = '.'+a;
    b = '.'+b;

    qca[0][0] = qca[0][1] = qca[0][2] = qcb[0][0] = qcb[0][1] = qcb[0][2] = 0;
    df[0][0][0] = df[0][0][1] = df[0][0][2] = df[0][1][0] = df[0][1][1] = df[0][1][2] = df[0][2][0] = df[0][2][1] = df[0][2][2] = 0;

    for (int i = 1; i <= n; i++) {
        qca[i][0] = qca[i-1][0];
        qca[i][1] = qca[i-1][1];
        qca[i][2] = qca[i-1][2];

        qcb[i][0] = qcb[i-1][0];
        qcb[i][1] = qcb[i-1][1];
        qcb[i][2] = qcb[i-1][2];

        df[i][0][0] = df[i-1][0][0];
        df[i][0][1] = df[i-1][0][1];
        df[i][0][2] = df[i-1][0][2];

        df[i][1][0] = df[i-1][1][0];
        df[i][1][1] = df[i-1][1][1];
        df[i][1][2] = df[i-1][1][2];

        df[i][2][0] = df[i-1][2][0];
        df[i][2][1] = df[i-1][2][1];
        df[i][2][2] = df[i-1][2][2];

        qca[i][id(a[i])]++;
        qcb[i][id(b[i])]++;
        df[i][id(a[i])][id(b[i])]++;
    }
}

int get_distance(int x, int y) {
    x++; y++;

    if (qca[y][0] - qca[x-1][0] != qcb[y][0] - qcb[x-1][0]) return -1;
    if (qca[y][1] - qca[x-1][1] != qcb[y][1] - qcb[x-1][1]) return -1;
    if (qca[y][2] - qca[x-1][2] != qcb[y][2] - qcb[x-1][2]) return -1;

    int cdf[3][3];

    cdf[0][0] = df[y][0][0] - df[x-1][0][0];
    cdf[0][1] = df[y][0][1] - df[x-1][0][1];
    cdf[0][2] = df[y][0][2] - df[x-1][0][2];

    cdf[1][0] = df[y][1][0] - df[x-1][1][0];
    cdf[1][1] = df[y][1][1] - df[x-1][1][1];
    cdf[1][2] = df[y][1][2] - df[x-1][1][2];

    cdf[2][0] = df[y][2][0] - df[x-1][2][0];
    cdf[2][1] = df[y][2][1] - df[x-1][2][1];
    cdf[2][2] = df[y][2][2] - df[x-1][2][2];

    int sum = 0;
    for (int i = 0; i <= 2; i++)
        for (int j = 0; j <= 2; j++)
            if (i != j) sum += cdf[i][j];

    return (sum+1)/2;
}

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