Submission #938727

#	Time	Username	Problem	Language	Result	Execution time	Memory
938727		Hugo1729	Mutating DNA (IOI21_dna)	C++17	0 / 100	29 ms	8532 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
	
string a,b;
int n;
int pref[100001][3][3]={0},pa[100001][3]={0},pb[100001][3]={0};
map<char,int> m;
	
void init(string c, string d) {
	a=c;b=d;
	n=a.size();
	m['A']=0;
	m['C']=1;
	m['T']=2;
	for(int i=0;i<n;i++){
		for(int j=0;j<3;j++){
			pa[i+1][j]=pa[i][j];
			pb[i+1][j]=pb[i][j];
			for(int k=0;k<3;k++){
				pref[i+1][j][k]=pref[i+1][j][k];
			}
		}
		pa[i+1][m[a[i]]]++;
		pb[i+1][m[b[i]]]++;
		pref[i+1][m[a[i]]][m[b[i]]]++;
	}
	
}
	
int get_distance(int x, int y) {
	int dista1=pa[y+1][0]-pa[x][0];
	int distb1=pb[y+1][0]-pb[x][0];
	int dista2=pa[y+1][1]-pa[x][1];
	int distb2=pb[y+1][1]-pb[x][1];
	
	if(dista1==distb1&&dista2==distb2){
		int ans=0,l=y-x+1;
		for(int i=0;i<3;i++){
			for(int j=0;j<=i;j++){
				int sus1=pref[y+1][i][j]-pref[x][i][j];
				int sus2=pref[y+1][j][i]-pref[x][j][i];
				if(i==j)l-=sus1;
				else{
					int sussy=min(sus1,sus2);
					l-=2*sussy;
					ans+=sussy;
				}
			}
		}
		int among=l/3;
		ans+=among*2;
		return ans;

	} else return -1;
}

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