Submission #1062385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062385		Ignut	Mutating DNA (IOI21_dna)	C++17	100 / 100	30 ms	10076 KiB

dna

/* Ignut
started: 17.08.2024
now: 17.08.2024
████████████████████████████████████████████████████████████████████
████████████████████████████████    ████████████████████████████████
██████████████████████████████        ██████████████████████████████
██████      ██████████████████        ██████████████████      ██████
██████          ██████████████        ██████████████          ██████
██████      ██    ████████████        ████████████    ██      ██████
██████      ████    ██████████        ██████████    ████      ██████
██████      ████      ██████████    ██████████      ████      ██████
██████      ████      ██████████    ██████████    ██████      ██████
██████      ██████    ██████████    ██████████    ██████      ██████
██████      ██████    ████████        ████████    ██████      ██████
██████      ██████      ██████        ██████      ██████      ██████
██████      ████        ████            ████        ████      ██████
██████            ██████████    ████    ██████████            ██████
██████      ██      ██████    ████████    ██████      ██      ██████
██████      ██████            ████████            ██████      ██████
██████                    ██            ██                    ██████
██████████████████████      ████    ████      ██████████████████████
████████████████████████      ██    ██      ████████████████████████
██████████████████████████                ██████████████████████████
██████████████████████████████        ██████████████████████████████
████████████████████████████████████████████████████████████████████
*/

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1e5 + 123;
string a, b;

vector<char> vec = {'A', 'C', 'T'};

map<char, int> pos;

int pref[N][3][3];
int pa[N][3];
int pb[N][3];

void init(string A, string B) {
    for (int i = 0; i < 3; i ++) pos[vec[i]] = i;
    a = A, b = B;
    int n = a.size();
    for (int i = 0; i < n; i ++) {
        for (int u = 0; u < 3; u ++) {
            pa[i + 1][u] = pa[i][u];
            pb[i + 1][u] = pb[i][u];
            for (int v = 0; v < 3; v ++)
                pref[i + 1][u][v] = pref[i][u][v];
        }
        pref[i + 1][pos[A[i]]][pos[B[i]]] ++;
        pa[i + 1][pos[A[i]]] ++;
        pb[i + 1][pos[B[i]]] ++;
    }
}


int get_distance(int x, int y) {
    int cntAx = pa[y + 1][0] - pa[x][0], cntCx = pa[y + 1][1] - pa[x][1];
    int cntAy = pb[y + 1][0] - pb[x][0], cntCy = pb[y + 1][1] - pb[x][1];
    if (cntAx != cntAy || cntCx != cntCy) return -1;

    int cntAT = pref[y + 1][0][2] - pref[x][0][2];
    int cntTA = pref[y + 1][2][0] - pref[x][2][0];
    int cntAC = pref[y + 1][0][1] - pref[x][0][1];
    int cntCA = pref[y + 1][1][0] - pref[x][1][0];
    int cntCT = pref[y + 1][1][2] - pref[x][1][2];
    int cntTC = pref[y + 1][2][1] - pref[x][2][1];
    int mn = min({abs(cntAT - cntTA), abs(cntAC - cntCA), abs(cntCT - cntTC)});
    int total = cntAT + cntTA + cntAC + cntCA + cntCT + cntTC;
    return (total - mn) / 2 + mn;
}

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