Submission #1190138

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190138		MrDogMeat	Mutating DNA (IOI21_dna)	C++20	100 / 100	24 ms	5644 KiB

dna

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

const int MAXN = 1e5 + 5;

int enc[256];
int N, A[MAXN], B[MAXN];
int cnt[MAXN], cc[3][MAXN], pref[2][MAXN];

void init(std::string a, std::string b) {
    enc['A'] = 0;
    enc['C'] = 1;
    enc['T'] = 2;
    int N = a.size();
    for(int i = 0; i < N; i++) {
        A[i + 1] = enc[a[i]];
        B[i + 1] = enc[b[i]];
    }
    for(int i = 1; i <= N; i++) {
        for(int j = 0; j < 3; j++) {
            cc[j][i] = cc[j][i - 1];
        }
        cnt[i] = cnt[i - 1];
        pref[0][i] = pref[0][i - 1];
        pref[1][i] = pref[1][i - 1];

        cc[A[i]][i]++;
        cc[B[i]][i]--;
        if(A[i] != B[i]) {
            cnt[i]++;
            if(A[i] == 0 && B[i] == 1) {
                pref[0][i]++;
            }
            if(A[i] == 1 && B[i] == 0) {
                pref[1][i]++;
            }
        }
    }
}

int get_distance(int x, int y) {
    x++, y++;
    for(int j = 0; j < 3; j++) {
        if(cc[j][y] - cc[j][x - 1] != 0) {
            return -1;
        }
    }

    int D = (pref[0][y] - pref[0][x - 1]) - (pref[1][y] - pref[1][x - 1]);
    if(D < 0) D = -D;
    int Ans = (cnt[y] - cnt[x - 1] - 3*D) / 2 + 2*D;
    return Ans;
}

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