Submission #618740

#	Time	Username	Problem	Language	Result	Execution time	Memory
618740		happypotato	Mutating DNA (IOI21_dna)	C++17	100 / 100	49 ms	9736 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 1e5 + 1;
int ps[mxN][3][3];
int check[2][mxN][3];
unordered_map<char, int> conv = {{'A', 0}, {'C', 1}, {'T', 2}};
int n;
void init(string a, string b) {
    n = a.length();
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            ps[0][i][j] = 0;
        }
        check[0][0][i] = check[1][0][i] = 0;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 3; k++) {
                ps[i][j][k] = ps[i - 1][j][k];
            }
            check[0][i][j] = check[0][i - 1][j];
            check[1][i][j] = check[1][i - 1][j];
        }
        ps[i][conv[a[i - 1]]][conv[b[i - 1]]]++;
        check[0][i][conv[a[i - 1]]]++;
        check[1][i][conv[b[i - 1]]]++;
    }
}
int get_distance(int x, int y) {
    x++; y++;
    for (int i = 0; i < 3; i++) {
        if (check[0][y][i] - check[0][x - 1][i] != check[1][y][i] - check[1][x - 1][i]) {
            return -1;
        }
    }
    int diff[6];
    diff[0] = ps[y][0][1] - ps[x - 1][0][1];
    diff[1] = ps[y][0][2] - ps[x - 1][0][2];
    diff[2] = ps[y][1][0] - ps[x - 1][1][0];
    diff[3] = ps[y][1][2] - ps[x - 1][1][2];
    diff[4] = ps[y][2][0] - ps[x - 1][2][0];
    diff[5] = ps[y][2][1] - ps[x - 1][2][1];
    int ans = 0;
    int cur;
    // 01
    cur = min(diff[0], diff[2]);
    diff[0] -= cur; diff[2] -= cur;
    ans += cur;
    // 02
    cur = min(diff[1], diff[4]);
    diff[1] -= cur; diff[4] -= cur;
    ans += cur;
    // 12
    cur = min(diff[3], diff[5]);
    diff[3] -= cur; diff[5] -= cur;
    ans += cur;
    // 012
    cur = min({diff[0], diff[3], diff[4]});
    diff[0] -= cur; diff[3] -= cur; diff[4] -= cur;
    ans += cur * 2;
    // 210
    cur = min({diff[5], diff[2], diff[1]});
    diff[5] -= cur; diff[2] -= cur; diff[1] -= cur;
    ans += cur * 2;
    return ans;
}

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