Submission #448141

#	Time	Username	Problem	Language	Result	Execution time	Memory
448141		hizuna	Mutating DNA (IOI21_dna)	C++17	100 / 100	47 ms	7416 KiB

dna

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

int f[100005][3][3];

int get_pair_cnt(int ca, int cb, int l, int r) {
    return f[r + 1][ca][cb] - f[l][ca][cb];
}

int ord(char c) {
    return c == 'A' ? 0 : (c == 'C' ? 1 : 2);
}

void init(std::string a, std::string b) {
    int sz = a.size(), orda, ordb;

    for(int k = 1; k <= sz; k++) {
        for(int i = 0; i < 3; i++) {
            for(int j = 0; j < 3; j++) {
                f[k][i][j] += f[k - 1][i][j];
            }
        }
        orda = ord(a[k - 1]), ordb = ord(b[k - 1]);
        if(orda != ordb) ++f[k][orda][ordb];
    } 
}

int get_distance(int x, int y) {
    int res = 0, charbal[3] = {};

    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 3; j++) {
            int pairs = get_pair_cnt(i, j, x, y);
            charbal[i] += pairs;
            charbal[j] -= pairs;
        }
    }

    for(int i = 0; i < 3; i++) {
        if(charbal[i] != 0) return -1;
    }

    int tot = 0;
    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 3; j++) {
            tot += get_pair_cnt(i, j, x, y);
        }
    }
    for(int i = 0; i < 3; i++) {
        for(int j = i + 1; j < 3; j++) {
            int cm = std::min(get_pair_cnt(i, j, x, y), get_pair_cnt(j, i, x, y));
            tot -= cm * 2;
            res += cm;
        }
    }

    res += (tot / 3) * 2;

    return res;
}

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