Submission #1185340

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185340		boclobanchat	Mutating DNA (IOI21_dna)	C++20	35 / 100	21 ms	4932 KiB

dna

#include"dna.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int pref[MAXN][6];
void init(string a,string b)
{
	int n=a.length();
	a=' '+a,b=' '+b;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<6;j++) pref[i][j]+=pref[i-1][j];
		if(a[i]=='A'&&b[i]=='T') pref[i][0]++;
		if(a[i]=='T'&&b[i]=='A') pref[i][3]++;
		if(a[i]=='T'&&b[i]=='C') pref[i][1]++;
		if(a[i]=='C'&&b[i]=='T') pref[i][4]++;
		if(a[i]=='C'&&b[i]=='A') pref[i][2]++;
		if(a[i]=='A'&&b[i]=='C') pref[i][5]++;
	}
}
int get_distance(int x,int y)
{
	x++,y++;
	int a0=pref[y][0]-pref[x-1][0];
	int a1=pref[y][1]-pref[x-1][1];
	int a2=pref[y][2]-pref[x-1][2];
	int a3=pref[y][3]-pref[x-1][3];
	int a4=pref[y][4]-pref[x-1][4];
	int a5=pref[y][5]-pref[x-1][5];
	int u=min(a0,a3),v=min(a1,a4),w=min(a2,a5);
	int ans=u+v+w;
	a0-=u,a3-=u,a1-=v,a4-=v,a2-=w,a5-=w;
	if(max(a0,a3)==max(a1,a4)&&max(a0,a3)==max(a2,a5)) return ans+max(a0,a3)*2;
	return -1;
}

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