Submission #523452

#	Time	Username	Problem	Language	Result	Execution time	Memory
523452		eecs	Mutating DNA (IOI21_dna)	C++17	100 / 100	45 ms	6232 KiB

dna

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

vector<int> pre[6];

void init(string a, string b) {
    int n = a.size();
    for (auto &vec : pre) vec.resize(n + 1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 6; j++) {
            pre[j][i + 1] = pre[j][i];
        }
        if (a[i] == 'A' && b[i] == 'T') pre[0][i + 1]++;
        if (a[i] == 'T' && b[i] == 'A') pre[3][i + 1]++;
        if (a[i] == 'T' && b[i] == 'C') pre[1][i + 1]++;
        if (a[i] == 'C' && b[i] == 'T') pre[4][i + 1]++;
        if (a[i] == 'C' && b[i] == 'A') pre[2][i + 1]++;
        if (a[i] == 'A' && b[i] == 'C') pre[5][i + 1]++;
    }
}

int get_distance(int x, int y) {
    int ans = 0, num[6];
    for (int i = 0; i < 6; i++) {
        num[i] = pre[i][y + 1] - pre[i][x];
    }
    for (int i = 0; i < 3; i++) {
        int t = min(num[i], num[i + 3]);
        ans += t, num[i] -= t, num[i + 3] -= t;
    }
    if (num[0] == num[1] && num[1] == num[2]) {
        if (!num[3] && !num[4] && !num[5]) return ans + num[0] * 2;
    }
    if (num[3] == num[4] && num[4] == num[5]) {
        if (!num[0] && !num[1] && !num[2]) return ans + num[3] * 2;
    }
    return -1;
}

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