Submission #1239346

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239346		Hamed_Ghaffari	Mutating DNA (IOI21_dna)	C++20	100 / 100	22 ms	6152 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;

const int MXN = 1e5+5;

int A[MXN], C[MXN], T[MXN], AC[MXN], CA[MXN], AT[MXN], TA[MXN], CT[MXN], TC[MXN];

void init(string a, string b) {
    for(int i=0; i<a.size(); i++) {
        A[i+1] = A[i] + (a[i]=='A') - (b[i]=='A');
        C[i+1] = C[i] + (a[i]=='C') - (b[i]=='C');
        T[i+1] = T[i] + (a[i]=='T') - (b[i]=='T');
        AC[i+1] = AC[i] + (a[i]=='A'&&b[i]=='C');
        CA[i+1] = CA[i] + (a[i]=='C'&&b[i]=='A');
        AT[i+1] = AT[i] + (a[i]=='A'&&b[i]=='T');
        TA[i+1] = TA[i] + (a[i]=='T'&&b[i]=='A');
        CT[i+1] = CT[i] + (a[i]=='C'&&b[i]=='T');
        TC[i+1] = TC[i] + (a[i]=='T'&&b[i]=='C');
    }
}

int get_distance(int x, int y) {
    if(A[y+1]-A[x] || C[y+1]-C[x] || T[y+1]-T[x]) return -1;
    int ac = AC[y+1]-AC[x];
    int ca = CA[y+1]-CA[x];
    int at = AT[y+1]-AT[x];
    int ta = TA[y+1]-TA[x];
    int ct = CT[y+1]-CT[x];
    int tc = TC[y+1]-TC[x];
    int tmp = min(ac, ca);
    int res = tmp;
    ac -= tmp;
    ca -= tmp;
    tmp = min(at, ta);
    res += tmp;
    at -= tmp;
    ta -= tmp;
    tmp = min(ct, tc);
    res += tmp;
    ct -= tmp;
    tc -= tmp;
    return res + 2*max({ac, ca, at, ta, ct, tc});
}

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