Submission #1062375

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062375		Ignut	Mutating DNA (IOI21_dna)	C++17	71 / 100	1578 ms	3924 KiB

dna

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

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

string a, b;

void init(string A, string B) {
    a = A, b = B;
}

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

int get_distance(int x, int y) {
    int cntAx = 0, cntCx = 0;
    int cntAy = 0, cntCy = 0;
    map<pair<char, char>, int> cnt;
    for (int i = x; i <= y; i ++) {
        if (a[i] == 'A') cntAx ++;
        else if (a[i] == 'C') cntCx ++;
        if (b[i] == 'A') cntAy ++;
        else if (b[i] == 'C') cntCy ++;
        cnt[{a[i], b[i]}] ++;
    }
    if (cntAx != cntAy || cntCx != cntCy) return -1;

    // int total = 0, mn = y - x + 1;
    // for (int i = 0; i < 3; i ++) {
    //     for (int j = 0; j < 3; j ++) {
    //         if (i == j) continue;
    //         total += cnt[{vec[i], vec[j]}];
    //         mn = min(mn, cnt[{vec[i], vec[j]}]);
    //     }
    // }
    int total = 0, mn = y - x + 1;
    mn = min({abs(cnt[{'A', 'T'}] - cnt[{'T', 'A'}]), abs(cnt[{'A', 'C'}] - cnt[{'C', 'A'}]), abs(cnt[{'C', 'T'}] - cnt[{'T', 'C'}])});
    for (int i = x; i <= y; i ++) total += (a[i] != b[i]);
    return (total - mn) / 2 + mn;
}

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