Submission #848363

#	Time	Username	Problem	Language	Result	Execution time	Memory
848363		toma_ariciu	Mutating DNA (IOI21_dna)	C++17	100 / 100	32 ms	10988 KiB

dna

#include <string>
#include <iostream>

using namespace std;

const int maxN = 100005;
int n, v1[maxN], v2[maxN], sp[maxN][10], sp1[maxN][3], sp2[maxN][3];

int getCode(char c) {
    if (c == 'A') {
        return 0;
    }
    if (c == 'C') {
        return 1;
    }
    if (c == 'T') {
        return 2;
    }
}

void initString(string s, int v[], int sp[maxN][3]) {
    for (int i = 1; i <= n; i++) {
        v[i] = getCode(s[i - 1]);
        for (int j = 0; j < 3; j++) {
            sp[i][j] = sp[i - 1][j];
        }
        sp[i][v[i]]++;
    }
}


void init(string a, string b) {
    n = (int) a.size();
    initString(a, v1, sp1);
    initString(b, v2, sp2);
    for (int i = 1; i <= n; i++) {
        int code = v1[i] * 3 + v2[i];
        for (int j = 0; j < 9; j++) {
            sp[i][j] = sp[i - 1][j];
        }
        sp[i][code]++;
    }
}

/// AC = 1
/// AT = 2
/// CA = 3
/// CT = 5
/// TA = 6
/// TC = 7

int get_distance(int x, int y) {
    y++;
    for (int j = 0; j < 3; j++) {
        if ((sp1[y][j] - sp1[x][j]) != (sp2[y][j] - sp2[x][j])) {
            return -1;
        }
    }
    int AC = sp[y][1] - sp[x][1];
    int AT = sp[y][2] - sp[x][2];
    int CA = sp[y][3] - sp[x][3];
    int CT = sp[y][5] - sp[x][5];
    int TA = sp[y][6] - sp[x][6];
    int TC = sp[y][7] - sp[x][7];
    int min1 = min(AC, CA), min2 = min(AT, TA), min3 = min(CT, TC);
    int ans = min1 + min2 + min3;
    AC -= min1; CA -= min1;
    AT -= min2; TA -= min2;
    CT -= min3; TC -= min3;
    ans += 2 * (AC + CA);
    return ans;
}

Compilation message (stderr)

dna.cpp: In function 'int getCode(char)':
dna.cpp:19:1: warning: control reaches end of non-void function [-Wreturn-type]
   19 | }
      | ^

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