Submission #440724

#	Time	Username	Problem	Language	Result	Execution time	Memory
440724		BT21tata	Mutating DNA (IOI21_dna)	C++17	100 / 100	43 ms	8532 KiB

dna

#include "dna.h"
#include "bits/stdc++.h"

using namespace std;

int a[100005][6], cnta[100005][3], cntb[100005][3] /* AC, AT, CA, CT, TA, TC */;

void init(string A, string B)
{
	for(int i=0; i<(int)A.length(); i++)
	{
		if(A[i]=='A' and B[i]=='C') a[i+1][0]=1;
		if(A[i]=='A' and B[i]=='T') a[i+1][1]=1;
		if(A[i]=='C' and B[i]=='A') a[i+1][2]=1;
		if(A[i]=='C' and B[i]=='T') a[i+1][3]=1;
		if(A[i]=='T' and B[i]=='A') a[i+1][4]=1;
		if(A[i]=='T' and B[i]=='C') a[i+1][5]=1;
		
		for(int j=0; j<6; j++)
			a[i+1][j]+=a[i][j];

		if(A[i]=='A') cnta[i+1][0]=1;
		if(A[i]=='C') cnta[i+1][1]=1;
		if(A[i]=='T') cnta[i+1][2]=1;

		if(B[i]=='A') cntb[i+1][0]=1;
		if(B[i]=='C') cntb[i+1][1]=1;
		if(B[i]=='T') cntb[i+1][2]=1;

		cnta[i+1][0]+=cnta[i][0];
		cnta[i+1][1]+=cnta[i][1];
		cnta[i+1][2]+=cnta[i][2];

		cntb[i+1][0]+=cntb[i][0];
		cntb[i+1][1]+=cntb[i][1];
		cntb[i+1][2]+=cntb[i][2];
	}
}

int get_distance(int x, int y)
{
	if(cnta[y+1][0]-cnta[x][0]!=cntb[y+1][0]-cntb[x][0] or
		cnta[y+1][1]-cnta[x][1]!=cntb[y+1][1]-cntb[x][1] or 
		cnta[y+1][2]-cnta[x][2]!=cntb[y+1][2]-cntb[x][2]) return -1;
	
	int num=0, ans=0, k;
	
	k=min(a[y+1][0]-a[x][0], a[y+1][2]-a[x][2]);
	num+=k;
	ans+=a[y+1][0]-a[x][0]-k;
	ans+=a[y+1][2]-a[x][2]-k;
	
	k=min(a[y+1][1]-a[x][1], a[y+1][4]-a[x][4]);
	num+=k;
	ans+=a[y+1][1]-a[x][1]-k;
	ans+=a[y+1][4]-a[x][4]-k;

	k=min(a[y+1][3]-a[x][3], a[y+1][5]-a[x][5]);
	num+=k;
	ans+=a[y+1][3]-a[x][3]-k;
	ans+=a[y+1][5]-a[x][5]-k;
	return num+ans/3*2;
}

/*
6 3
ATACAT
ACTATA
1 3
4 5
3 5
*/

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