Submission #533122

#	Time	Username	Problem	Language	Result	Execution time	Memory
533122		VodkaInTheJar	Mutating DNA (IOI21_dna)	C++17	100 / 100	42 ms	9740 KiB

dna

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

using namespace std;

const int maxn = 1e5 + 3;

int get_code(char ch) {
    if (ch == 'A')
        return 0;

    if (ch == 'C')
        return 1;

    return 2;
}

int cnt[maxn][3][3], cnt1[maxn][3], cnt2[maxn][3];
void init(string a, string b) {
    for (int i = 0; i < (int)a.size(); i++) {
        for (int j = 0; j < 3; j++)
            for (int k = 0; k < 3; k++)
                cnt[i][j][k] = (i ? cnt[i-1][j][k] : 0);

        cnt[i][get_code(a[i])][get_code(b[i])]++;
        for (int j = 0; j < 3; j++) {
            cnt1[i][j] = (i ? cnt1[i - 1][j] : 0);
            cnt2[i][j] = (i ? cnt2[i - 1][j] : 0);
        }

        cnt1[i][get_code(a[i])]++;
        cnt2[i][get_code(b[i])]++;
    }
}

int temp[3][3];
int get_distance(int l, int r) {
    for (int i = 0; i < 3; i++)
        if (cnt1[r][i] - cnt1[l-1][i] != cnt2[r][i] - cnt2[l-1][i])
            return -1;

    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            temp[i][j] = cnt[r][i][j] - cnt[l-1][i][j];

    int ans = 0, left = r - l + 1;
    for (int i = 0; i < 3; i++)
        for (int j = i + 1; j < 3; j++) {
            int mins = min(temp[i][j], temp[j][i]);
            temp[i][j] -= mins;
            temp[j][i] -= mins;
            ans += mins;
            left -= mins * 2;
        }

    for (int i = 0; i < 3; i++)
        left -= temp[i][i];

    ans += left * 2 / 3;
    return ans;
}

/*
int main() {
    init("ATACAT", "ACTATA");
    cout << get_distance(4, 5) << endl;
}
 */

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