Submission #551315

#	Time	Username	Problem	Language	Result	Execution time	Memory
551315		Pherokung	Mutating DNA (IOI21_dna)	C++17	100 / 100	45 ms	7808 KiB

dna

#include "dna.h"
#include<bits/stdc++.h>
#define N 100005
using namespace std;
int a[N][9],dif[N],len,rev[9];
map<char,int> mp;
void init(string x, string y) {
	len = x.size();
	mp['A'] = 0, mp['T'] = 1, mp['C'] = 2;
	for(int i=0;i<=8;i++){
		if(i % 4 != 0){
			int k1 = i/3, k2 = i % 3;
			rev[i] = k2*3 + k1;
		}
	}
	for(int i=0;i<len;i++){
		if(i != 0) for(int j=0;j<=8;j++) a[i][j] = a[i-1][j];
		a[i][mp[x[i]]*3 + mp[y[i]]]++;
		if(i != 0) dif[i] = dif[i-1];
		if(x[i] != y[i]) dif[i]++;
	}
}

int get_distance(int x, int y) {
	int A[9], D;
	for(int i=0;i<=8;i++) A[i] = a[y][i];
	if(x != 0) for(int i=0;i<=8;i++) A[i] -= a[x-1][i];
//	for(int i=0;i<=8;i++) printf(">>%d\n",A[i]); 
//	printf("======\n");
	for(int i=0;i<=2;i++){
		int k1 = 0, k2 = 0;
		for(int j=0;j<=8;j++){
			if(j / 3 == i) k1+=A[j];
			if(j % 3 == i) k2+=A[j];
		}
		if(k1 != k2) return -1;
	}
	int ans = 0, cnt = 0;
	for(int i=0;i<=8;i++) if(i % 4 == 0) A[i] = 0;
	for(int i=0;i<=8;i++){
		int k = min(A[i],A[rev[i]]);
		ans += k, A[i] -= k, A[rev[i]] -= k;
	}
	
	int k;
	k = min({A[2],A[3],A[7]});
	ans += k*2;
	A[2] -= k, A[3] -= k, A[7] -= k;
	
	k = min({A[1],A[5],A[6]});
	ans += k*2;
	A[1] -= k, A[5] -= k, A[6] -= k;
	
	for(int i=0;i<=8;i++) cnt += A[i];
	cnt = max(cnt-1,0);
	return ans + cnt;
}

Compilation message (stderr)

dna.cpp: In function 'int get_distance(int, int)':
dna.cpp:25:12: warning: unused variable 'D' [-Wunused-variable]
   25 |  int A[9], D;
      |            ^

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