Submission #622277

#	Time	Username	Problem	Language	Result	Execution time	Memory
622277		alirezasamimi100	Mutating DNA (IOI21_dna)	C++17	100 / 100	47 ms	7400 KiB

dna

#include "dna.h"
using namespace std;

const int N = 1e5 + 10;

int ps[3][3][N],n;

void init(string a, string b) {
    n=a.size();
    for(int i=0; i<n; i++){
        if(i){
            for(int j=0; j<3; j++){
                for(int k=0; k<3; k++){
                    ps[j][k][i]=ps[j][k][i-1];
                }
            }
        }
        int x=2,y=2;
        if(a[i]=='A') x=0;
        if(a[i]=='C') x=1;
        if(b[i]=='A') y=0;
        if(b[i]=='C') y=1;
        ps[x][y][i]++;
    }
}

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

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