Submission #444171

#	Time	Username	Problem	Language	Result	Execution time	Memory
444171		urd05	Mutating DNA (IOI21_dna)	C++17	100 / 100	47 ms	9756 KiB

dna

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

int asum[3][100001];
int bsum[3][100001];
int c[3]={'A','T','C'};
int atc[9][100001];

void init(string a, string b) {
    int n=a.size();
    for(int i=1;i<=n;i++) {
        for(int j=0;j<3;j++) {
            if (a[i-1]==c[j]) {
                asum[j][i]=asum[j][i-1]+1;
            }
            else {
                asum[j][i]=asum[j][i-1];
            }
            if (b[i-1]==c[j]) {
                bsum[j][i]=bsum[j][i-1]+1;
            }
            else {
                bsum[j][i]=bsum[j][i-1];
            }
        }
    }
    for(int i=1;i<=n;i++) {
        int val=0;
        for(int j=0;j<3;j++) {
            if (a[i-1]==c[j]) {
                val+=j*3;
            }
            if (b[i-1]==c[j]) {
                val+=j;
            }
        }
        for(int j=0;j<9;j++) {
            atc[j][i]=atc[j][i-1]+(val==j);
        }
    }
}

int get_distance(int x, int y) {
    x++;
    y++;
    for(int j=0;j<3;j++) {
        if (asum[j][y]-asum[j][x-1]!=bsum[j][y]-bsum[j][x-1]) {
            return -1;
        }
    }
	int AT=atc[1][y]-atc[1][x-1];
	int TA=atc[3][y]-atc[3][x-1];
	int AC=atc[2][y]-atc[2][x-1];
	int CA=atc[6][y]-atc[6][x-1];
	int TC=atc[5][y]-atc[5][x-1];
	int CT=atc[7][y]-atc[7][x-1];
	return min(AT,TA)+min(AC,CA)+min(TC,CT)+max(AT-TA,TA-AT)*2;
}

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