Submission #677185

#	Time	Username	Problem	Language	Result	Execution time	Memory
677185		bene42	Mutating DNA (IOI21_dna)	C++17	100 / 100	42 ms	8584 KiB

dna

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

using namespace std;

int A1[100005], T1[100005], C1[100005];
int A2[100005], T2[100005], C2[100005];

int AT[100005], AC[100005], TA[100005], TC[100005], CA[100005], CT[100005];

void init(std::string a, std::string b) {
    for (int i = 0; i < a.size(); i++) {
        if (i > 0) {
            A1[i] = A1[i - 1];
            T1[i] = T1[i - 1];
            C1[i] = C1[i - 1];
            A2[i] = A2[i - 1];
            T2[i] = T2[i - 1];
            C2[i] = C2[i - 1];

            AT[i] = AT[i - 1];
            AC[i] = AC[i - 1];
            TA[i] = TA[i - 1];
            TC[i] = TC[i - 1];
            CA[i] = CA[i - 1];
            CT[i] = CT[i - 1];
        }
        A1[i] += a[i] == 'A' ? 1 : 0;
        T1[i] += a[i] == 'T' ? 1 : 0;
        C1[i] += a[i] == 'C' ? 1 : 0;
        A2[i] += b[i] == 'A' ? 1 : 0;
        T2[i] += b[i] == 'T' ? 1 : 0;
        C2[i] += b[i] == 'C' ? 1 : 0;

        if (a[i] != b[i]) {
            if (b[i] == 'A') {
                TA[i] += a[i] == 'T' ? 1 : 0;
                CA[i] += a[i] == 'C' ? 1 : 0;
            } else {
                if (b[i] == 'T') {
                    AT[i] += a[i] == 'A' ? 1 : 0;
                    CT[i] += a[i] == 'C' ? 1 : 0;
                } else {
                    AC[i] += a[i] == 'A' ? 1 : 0;
                    TC[i] += a[i] == 'T' ? 1 : 0;
                }
            }
        }
    }
}

int get_distance(int x, int y) {
    int dA, dT, dC, dist = 0;
    dA = (A1[y] - (x == 0 ? 0 : A1[x - 1])) - (A2[y] - (x == 0 ? 0 : A2[x - 1]));
    dT = (T1[y] - (x == 0 ? 0 : T1[x - 1])) - (T2[y] - (x == 0 ? 0 : T2[x - 1]));
    dC = (C1[y] - (x == 0 ? 0 : C1[x - 1])) - (C2[y] - (x == 0 ? 0 : C2[x - 1]));


    if (dA != 0 || dT != 0 || dC != 0) {
        return -1;
    }

    int at = AT[y] - (x == 0 ? 0 : AT[x - 1]);
    int ac = AC[y] - (x == 0 ? 0 : AC[x - 1]);
    int ta = TA[y] - (x == 0 ? 0 : TA[x - 1]);
    int tc = TC[y] - (x == 0 ? 0 : TC[x - 1]);
    int ca = CA[y] - (x == 0 ? 0 : CA[x - 1]);
    int ct = CT[y] - (x == 0 ? 0 : CT[x - 1]);


    if (at >= ta) {
        dist += ta;
        at -= ta;
        ta = 0;
    } else {
        dist += at;
        ta -= at;
        at = 0;
    }
    if (tc >= ct) {
        dist += ct;
        tc -= ct;
        ct = 0;
    } else {
        dist += tc;
        ct -= tc;
        tc = 0;
    }
    if (ca >= ac) {
        dist += ac;
        ca -= ac;
        ac = 0;
    } else {
        dist += ca;
        ac -= ca;
        ca = 0;
    }
    
    dist += 2 * (at + ac + ta + tc + ca + ct) / 3;

    return dist;
}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:12:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for (int i = 0; i < a.size(); i++) {
      |                     ~~^~~~~~~~~~

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