Submission #1275771

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275771		nhamtan	Mutating DNA (IOI21_dna)	C++20	56 / 100	32 ms	9708 KiB

dna

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

const int N = 1e5 + 5;
char c[] = {'A', 'C', 'T'};

int n;
int pre[N][3][3], preTwo[N][3][3], cnt[3][3], dem[3][3];

void init(string A, string B) {
    n = A.size();

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 3; j++)
        for (int k = 0; k < 3; k++) {
            pre[i][j][k] = pre[i-1][j][k] + 
                (A[i-1] != B[i-1] && A[i-1] == c[j] && B[i-1] == c[k]);

            preTwo[i][j][k] = preTwo[i-1][j][k] + 
                (A[i-1] != B[i-1] && B[i-1] == c[j] && A[i-1] == c[k]);
        }
    }
}

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

    for (int j = 0; j < 3; j++) {
        for (int k = 0; k < 3; k++) {
            cnt[j][k] = pre[y][j][k] - pre[x-1][j][k];
            dem[j][k] = preTwo[y][j][k] - preTwo[x-1][j][k];
        }

        if (cnt[j][0] + cnt[j][1] + cnt[j][2] != 
            dem[j][0] + dem[j][1] + dem[j][2]) return -1;
    }

    int ans = 0;

    // đổi chéo trực tiếp
    for (int j = 0; j < 3; j++)
    for (int k = 0; k < 3; k++) {
        int temp = min(cnt[j][k], cnt[k][j]);
        cnt[j][k] -= temp;
        cnt[k][j] -= temp;
        ans += temp;
    }

    bool ok = false;
    for (int j = 0; j < 3; j++)
    for (int k = 0; k < 3; k++) {
        ans += cnt[j][k];
        if (cnt[j][k]) ok = true;
    }

    ans -= ok; // trừ đi 1 nếu có chu trình 3 ký tự

    return ans;
}

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