Submission #466476

#	Time	Username	Problem	Language	Result	Execution time	Memory
466476		alexxela12345	Mutating DNA (IOI21_dna)	C++17	100 / 100	144 ms	23712 KiB

dna

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

int n;
vector<vector<vector<int>>> pref;

void init(std::string a, std::string b) {
    n = a.size();
    pref.resize(n + 1, vector<vector<int>> (3, vector<int> (3)));
    for (int i = 0; i < n; i++) {
        pref[i + 1] = pref[i];
        int a1;
        if (a[i] == 'A') {
            a1 = 0;
        } else if (a[i] == 'C') {
            a1 = 1;
        } else {
            a1 = 2;
        }
        int b1;
        if (b[i] == 'A') {
            b1 = 0;
        } else if (b[i] == 'C') {
            b1 = 1;
        } else {
            b1 = 2;
        }
        pref[i + 1][a1][b1]++;
    }
}

int get_distance(int x, int y) {
    vector<vector<int>> arr = pref[y + 1];
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            arr[i][j] -= pref[x][i][j];
        }
    }
    vector<int> cnt1(3), cnt2(3);
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            cnt1[i] += arr[i][j];
            cnt2[j] += arr[i][j];
        }
    }
    if (cnt1 != cnt2) {
        return -1;
    }
    for (int i = 0; i < 3; i++) {
        arr[i][i] = 0;
    }
    int ans = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            int mn = min(arr[i][j], arr[j][i]);
            ans += mn;
            arr[i][j] -= mn;
            arr[j][i] -= mn;
        }
    }
    assert(arr[0][1] == arr[1][2] && arr[1][2] == arr[2][0]);    
    assert(arr[1][0] == arr[2][1] && arr[2][1] == arr[0][2]);    
    ans += 2 * (arr[0][1] + arr[1][0]);
	return ans;
}

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