Submission #438735

#	Time	Username	Problem	Language	Result	Execution time	Memory
438735		Tc14	Mutating DNA (IOI21_dna)	C++17	100 / 100	66 ms	9832 KiB

dna

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "dna.h"
using namespace std;
#define ve vector
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9 + 10;

int n;
ve<ve<int>> C;
ve<ve<ve<int>>> F;
ve<pair<char, char>> X = {
    {'A', 'C'}, {'C', 'A'}, 
    {'A', 'T'}, {'T', 'A'},
    {'C', 'T'}, {'T', 'C'},
};
ve<char> I = {'A', 'C', 'T'};

void init(string A, string B) {

    n = (int)A.size();
    C = ve<ve<int>>(6, ve<int>(n + 1));
    F = ve<ve<ve<int>>>(3, ve<ve<int>>(2, ve<int>(n + 1)));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 6; j++) {
            int x = A[i] == X[j].first && B[i] == X[j].second;
            C[j][i + 1] = C[j][i] + x;
        }
        for (int j = 0; j < 3; j++) {
            F[j][0][i + 1] = F[j][0][i] + (A[i] == I[j]);
            F[j][1][i + 1] = F[j][1][i] + (B[i] == I[j]);
        }
    }
}

int get_distance(int x, int y) {

    ve<int> P(6);
    for (int i = 0; i < 6; i++) {
        P[i] = C[i][y + 1] - C[i][x];
    }

    for (int i = 0; i < 3; i++) {
        int a = F[i][0][y + 1] - F[i][0][x];
        int b = F[i][1][y + 1] - F[i][1][x];
        if (a != b) return -1;
    }

    int ans = 0;

    ans += min(P[0], P[1]);
    ans += min(P[2], P[3]);
    ans += min(P[4], P[5]);

    ans += 2 * abs(P[0] - P[1]);

    return ans;
}

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