Submission #1101045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101045		nicholask	Mutating DNA (IOI21_dna)	C++17	100 / 100	33 ms	9984 KiB

dna

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

int fa[100010][3],fb[100010][3],cnt[100010][3][3];
void init(string a,string b){
    int n=a.size();
    a=" "+a; b=" "+b;
    for (int i=1; i<=n; i++){
        for (int j=0; j<3; j++) fa[i][j]=fa[i-1][j];
        int ca,cb;
        if (a[i]=='A') ca=0;
        else if (a[i]=='T') ca=1;
        else ca=2;
        for (int j=0; j<3; j++) fb[i][j]=fb[i-1][j];
        if (b[i]=='A') cb=0;
        else if (b[i]=='T') cb=1;
        else cb=2;
        fa[i][ca]++; fb[i][cb]++;
        for (int j=0; j<3; j++){
            for (int k=0; k<3; k++) cnt[i][j][k]=cnt[i-1][j][k];
        }
        cnt[i][ca][cb]++;
    }
}

int get_distance(int x,int y){
	y++;
    for (int i=0; i<3; i++){
        if (fa[y][i]-fa[x][i]!=fb[y][i]-fb[x][i]) return -1;
    }
    int ans=0,tp[3][3];
    for (int i=0; i<3; i++){
        for (int j=0; j<3; j++) tp[i][j]=cnt[y][i][j]-cnt[x][i][j];
    }
    int t=min(tp[0][1],tp[1][0]);
    tp[0][1]-=t; tp[1][0]-=t; ans+=t;
    t=min(tp[0][2],tp[2][0]);
    tp[0][2]-=t; tp[2][0]-=t; ans+=t;
    t=min(tp[1][2],tp[2][1]);
    tp[1][2]-=t; tp[2][1]-=t; ans+=t;
    t=min({tp[0][1],tp[1][2],tp[2][0]});
    ans+=2*t;
    t=min({tp[1][0],tp[2][1],tp[0][2]});
    ans+=2*t;
    return ans;
}

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