Submission #583491

#	Time	Username	Problem	Language	Result	Execution time	Memory
583491		SlavicG	Mutating DNA (IOI21_dna)	C++17	100 / 100	44 ms	7220 KiB

dna

#include "dna.h"
using namespace std;
const int N = 1e5 + 10;
int p[N][6], cnta[N][3], cntb[N][3];

void init(std::string a, std::string b) {
    int n = a.size();
    for(int i = 1; i <= n; ++i) {
        for(int j = 0; j < 6; ++j) p[i][j] = p[i - 1][j];
        if(a[i - 1] == 'A' && b[i - 1] == 'T') ++p[i][0];
        if(a[i - 1] == 'T' && b[i - 1] == 'A') ++p[i][1];
        if(a[i - 1] == 'A' && b[i - 1] == 'C') ++p[i][2];
        if(a[i - 1] == 'C' && b[i - 1] == 'A') ++p[i][3];
        if(a[i - 1] == 'T' && b[i - 1] == 'C') ++p[i][4];
        if(a[i - 1] == 'C' && b[i - 1] == 'T') ++p[i][5];
        for(int j = 0; j < 3; ++j) cnta[i][j] = cnta[i - 1][j], cntb[i][j] = cntb[i - 1][j];

        if(a[i - 1] == 'A') cnta[i][0]++;
        else if(a[i - 1] == 'C') cnta[i][1]++;
        else cnta[i][2]++;

        if(b[i - 1] == 'A') cntb[i][0]++;
        else if(b[i - 1] == 'C') cntb[i][1]++;
        else cntb[i][2]++;
    }
}

int get_distance(int x, int y) {
    ++x, ++y;
    int AT = p[y][0] - p[x - 1][0], TA = p[y][1] - p[x - 1][1], AC = p[y][2] - p[x - 1][2];
    int CA = p[y][3] - p[x - 1][3], TC = p[y][4] - p[x - 1][4], CT = p[y][5] - p[x - 1][5];
    for(int j = 0; j < 3; ++j) if(cnta[y][j] - cnta[x - 1][j] != cntb[y][j] - cntb[x - 1][j]) return -1;

    int ans = 0;
    int f = min(AT, TA); ans += f;
    AT -= f, TA -= f;
    f = min(AC, CA); ans += f;
    AC -= f, CA -= f;
    f = min(TC, CT); ans += f;
    TC -= f, CT -= f;

    ans += (AT + TA + AC + CA + TC + CT) / 3 * 2;
    return ans;
}

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