Submission #1034822

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034822		ArthuroWich	Mutating DNA (IOI21_dna)	C++17	100 / 100	34 ms	9240 KiB

dna

#include "dna.h"
#include<bits/stdc++.h>
using namespace std;
int prefa[100005][2], preft[100005][2], prefc[100005][2], prefmiss[100005], prefcomb[100005][6];
void init(string a, string b) {
    int n = a.length();
    for (int i = 1; i <= n; i++) {
        prefa[i][0] = prefa[i-1][0] + (a[i-1]=='A');
        prefa[i][1] = prefa[i-1][1] + (b[i-1]=='A');
        preft[i][0] = preft[i-1][0] + (a[i-1]=='T');
        preft[i][1] = preft[i-1][1] + (b[i-1]=='T');
        prefc[i][0] = prefc[i-1][0] + (a[i-1]=='C');
        prefc[i][1] = prefc[i-1][1] + (b[i-1]=='C');
        prefmiss[i] = prefmiss[i-1] + (a[i-1]!=b[i-1]);
        prefcomb[i][0] = prefcomb[i-1][0];
        prefcomb[i][1] = prefcomb[i-1][1];
        prefcomb[i][2] = prefcomb[i-1][2];
        prefcomb[i][3] = prefcomb[i-1][3];
        prefcomb[i][4] = prefcomb[i-1][4];
        prefcomb[i][5] = prefcomb[i-1][5];
        if (a[i-1] == 'A' && b[i-1] == 'T') {
            prefcomb[i][0]++;
        }
        if (a[i-1] == 'T' && b[i-1] == 'A') {
            prefcomb[i][1]++;
        }
        if (a[i-1] == 'A' && b[i-1] == 'C') {
            prefcomb[i][2]++;
        }
        if (a[i-1] == 'C' && b[i-1] == 'A') {
            prefcomb[i][3]++;
        }
        if (a[i-1] == 'C' && b[i-1] == 'T') {
            prefcomb[i][4]++;
        }
        if (a[i-1] == 'T' && b[i-1] == 'C') {
            prefcomb[i][5]++;
        }
    }
}
int get_distance(int x, int y) {
    y++;
    if (prefa[y][0]-prefa[x][0] != prefa[y][1]-prefa[x][1]) {
        return -1;
    }
    if (preft[y][0]-preft[x][0] != preft[y][1]-preft[x][1]) {
        return -1;
    }
    if (preft[y][0]-preft[x][0] != preft[y][1]-preft[x][1]) {
        return -1;
    }
    if (prefmiss[y]-prefmiss[x] == 1) {
        return -1;
    }
    if (prefmiss[y]-prefmiss[x] == 0) {
        return 0;
    }
    int ans = min(prefcomb[y][0]-prefcomb[x][0], prefcomb[y][1]-prefcomb[x][1])+min(prefcomb[y][2]-prefcomb[x][2], prefcomb[y][3]-prefcomb[x][3])+min(prefcomb[y][4]-prefcomb[x][4], prefcomb[y][5]-prefcomb[x][5]);
    return ans+(prefmiss[y]-prefmiss[x]-2*ans)/3*2;
}

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